http://acm.hdu.edu.cn/showproblem.php?pid=1026
求起点到终点的最少花费，输出路径的时候麻烦一点，借鉴了别人的思路，用dfs 递归打印出路径。
用额外一个二维数组标记当前点的前驱，因为点是一个坐标，那么可以用 s=x*m+y 映射成一个点就可以了。
这样知道这个数值在求出坐标的话，x=s/m,y=s%m。
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <vector> 5 #include <cstring> 6 #include <string> 7 #include <algorithm> 8 #include <string> 9 #include <set> 10 #include <functional> 11 #include <numeric> 12 #include <sstream> 13 #include <stack> 14 #include <map> 15 #include <queue> 16 #pragma comment(linker, "/STACK:102400000,102400000") 17 #define CL(arr, val) memset(arr, val, sizeof(arr)) 18 19 #define ll long long 20 #define inf 0x7f7f7f7f 21 #define lc l,m,rt<<1 22 #define rc m + 1,r,rt<<1|1 23 #define pi acos(-1.0) 24 25 #define L(x) (x) << 1 26 #define R(x) (x) << 1 | 1 27 #define MID(l, r) (l + r) >> 1 28 #define Min(x, y) (x) < (y) ? (x) : (y) 29 #define Max(x, y) (x) < (y) ? (y) : (x) 30 #define E(x) (1 << (x)) 31 #define iabs(x) (x) < 0 ? -(x) : (x) 32 #define OUT(x) printf("%I64d\n", x) 33 #define lowbit(x) (x)&(-x) 34 #define Read() freopen("a.txt", "r", stdin) 35 #define Write() freopen("b.txt", "w", stdout); 36 #define maxn 1000000000 37 #define N 2510 38 #define mod 1000000000 39 using namespace std; 40 41 char field[110][110]; 42 int used[110][110]; 43 int n,m,time; 44 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 45 struct point 46 { 47 int x,y,step; 48 bool operator < (const point a) const 49 { 50 return step>a.step; 51 } 52 }; 53 int bfs() 54 { 55 point s; 56 s.x=0,s.y=0,s.step=0; 57 priority_queue<point>que; 58 que.push(s); 59 while(!que.empty()) 60 { 61 point e=que.top(); 62 que.pop(); 63 if(e.x==n-1&&e.y==m-1) return e.step; 64 for(int i=0;i<4;i++) 65 { 66 s=e; 67 s.x=e.x+dir[i][0]; 68 s.y=e.y+dir[i][1]; 69 if(s.x>=0&&s.x<n&&s.y>=0&&s.y<m&&field[s.x][s.y]!='X'&&used[s.x][s.y]==-1) 70 { 71 used[s.x][s.y]=e.x*m+e.y; 72 s.step+=1; 73 char c=field[s.x][s.y]; 74 if(c>='0'&&c<='9') s.step+=c-'0'; 75 //printf("%d %d %d\n",e.x,e.y,e.step); 76 que.push(s); 77 } 78 } 79 } 80 return 0; 81 } 82 83 void get_path(int x,int y) 84 { 85 if(x==0&&y==0) return; 86 // printf("%d\n",used[x][y]); 87 int a=used[x][y]/m,b=used[x][y]%m; 88 get_path(a,b); 89 printf("%ds:(%d,%d)->(%d,%d)\n",time++,a,b,x,y); 90 if(field[x][y]>='0'&&field[x][y]<='9') 91 { 92 while(field[x][y]>'0') 93 { 94 printf("%ds:FIGHT AT (%d,%d)\n",time++,x,y); 95 field[x][y]--; 96 } 97 } 98 } 99 int main() 100 { 101 // freopen("a.txt","r",stdin); 102 while(~scanf("%d%d",&n,&m)) 103 { 104 getchar(); 105 for(int i=0;i<n;i++) 106 { 107 scanf("%s",field[i]); 108 } 109 memset(used,-1,sizeof(used)); 110 int flag=bfs(); 111 if(flag) 112 { 113 printf("It takes %d seconds to reach the target position, let me show you the way.\n",flag); 114 time=1; 115 get_path(n-1,m-1); 116 } 117 else printf("God please help our poor hero.\n"); 118 printf("FINISH\n"); 119 } 120 return 0; 121 }