题意是要穿过一个迷宫并且将每一步打印出来。
用宽搜的方法找到路径，在 vis 中存一下方向，只是这题被看到的一种不太对的运算符重载坑了很久......
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 105; 4 char mp[maxn][maxn]; 5 int n,m,t,cnt,vis[maxn][maxn],fight[maxn][maxn]; 6 int dir[4][2] = {1,0,0,1,-1,0,0,-1}; 7 struct node 8 { 9 int x,y,time; 10 bool operator<(const node &a) const { 11 return a.time<time; 12 } 13 // 不能用的重载 14 // friend bool operator < (node a,node b) 15 // { 16 // return a.time < b.time; 17 // } 18 }; 19 //struct cmp 20 //{ 21 // bool operator () (node a,node b) 22 // { 23 // return a.time < b.time; 24 // } 25 //}; 26 bool bfs() 27 { 28 priority_queue<node> q; 29 // priority_queue<node,vector<node>,cmp> q; 30 node st; 31 st.x = st.y = st.time = 0; 32 q.push(st); 33 mp[0][0] = 'X'; 34 while (!q.empty()) 35 { 36 node cur = q.top(); 37 q.pop(); 38 if(cur.x==n-1 && cur.y==m-1) 39 { 40 t = cur.time; 41 return true; 42 } 43 for(int i = 0; i < 4; ++i) 44 { 45 node next; 46 next.x = cur.x+dir[i][0]; 47 next.y = cur.y+dir[i][1]; 48 if(mp[next.x][next.y]=='X') continue; 49 if(next.x<n && next.x>=0 && next.y<m && next.y>=0 ) 50 { 51 if(mp[next.x][next.y]!='.') 52 { 53 next.time = cur.time+1+mp[next.x][next.y]-'0'; 54 fight[next.x][next.y] = mp[next.x][next.y]-'0'; 55 } 56 else next.time = cur.time+1; 57 vis[next.x][next.y] = i+1; 58 q.push(next); 59 mp[next.x][next.y] = 'X'; 60 } 61 } 62 } 63 return false; 64 } 65 void prtmp(int x,int y) 66 { 67 if(vis[x][y] == 0) return ; 68 int prex,prey; 69 prex = x - dir[vis[x][y]-1][0]; 70 prey = y - dir[vis[x][y]-1][1]; 71 prtmp(prex,prey); 72 cout << (cnt++) << "s:(" << prex << "," << prey << ")->(" << x << "," << y << ") "; 73 while(fight[x][y]--) 74 cout << (cnt++) << "s:FIGHT AT (" << x << "," << y << ") "; 75 } 76 int main() 77 { 78 while(cin >> n >> m) 79 { 80 memset(fight,0,sizeof(fight)); 81 memset(vis,0,sizeof(vis)); 82 for(int i = 0; i < n; ++i) 83 for(int j = 0; j < m; ++j) 84 cin >> mp[i][j]; 85 if(bfs()) 86 { 87 cnt = 1; 88 cout << "It takes " << t << " seconds to reach the target position, let me show you the way. "; 89 prtmp(n-1,m-1); 90 } 91 else cout << "God please help our poor hero. "; 92 cout << "FINISH "; 93 } 94 return 0; 95 }