解题思路：打印路径是关键，细节处理见代码。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn = 105; 6 char mapp[maxn][maxn]; 7 int q[maxn*maxn*4][2]; //队列，刚开始没有乘以4，结果RE了 8 //dp[i][j]表示走到坐标(i,j)时所用的时间 9 //pre[x][y]存储当前点的前一个点在队列中的位置 10 int pre[maxn][maxn], dp[maxn][maxn], n, m, f, r, tmp, t; 11 int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; 12 13 void bfs() 14 { 15 f = 0, r = 1; //f为头指针，r为尾指针 16 q[0][0] = 0, q[0][1] = 0, dp[0][0] = 0; 17 18 while(f != r) 19 { 20 int x = q[f][0], y = q[f][1]; 21 tmp = f; //与32行对应 22 f ++; //出队列 23 24 for(int i = 0; i < 4; i++) 25 { 26 int xx = x + dir[i][0]; 27 int yy = y + dir[i][1]; 28 int tt = dp[x][y] + 1; 29 if(xx < 0 || xx >= n || yy < 0 || yy >= m || mapp[xx][yy] == 'X') continue; 30 //如果当前点之前到达过，并且所用的时间小于或等于当前点，进行下一次循环。 31 if(dp[xx][yy] != -1 && dp[xx][yy] <= tt) continue; 32 if(mapp[xx][yy] != '.') tt += mapp[xx][yy] - '0'; //遇到怪兽，原地扁他 33 pre[xx][yy] = tmp, q[r][0] = xx, q[r][1] = yy, dp[xx][yy] = tt, r ++; 34 } 35 } 36 return ; 37 } 38 39 int Print(int x,int y) 40 { 41 int k = pre[x][y]; 42 43 if(pre[x][y] == -1) return 0; //不能走，则返回； 44 Print(q[k][0], q[k][1]); //好好体会这里的递归。 45 46 printf("%ds:(%d,%d)->(%d,%d) ", t++, q[k][0], q[k][1], x, y); 47 if(mapp[x][y] != '.') //说明是怪兽，原地痛打 48 for(int i = 0; i < mapp[x][y] - '0'; i++) //数字多大就打多久 49 printf("%ds:FIGHT AT (%d,%d) ", t++, x, y); 50 return 0; 51 } 52 53 int main() 54 { 55 while(~scanf("%d %d", &n, &m)) 56 { 57 for(int i = 0; i < n; i++) 58 for(int j = 0; j < m; j++) scanf(" %c", &mapp[i][j]); 59 60 memset(dp, -1, sizeof(dp)); //都初始化为没有访问过 61 memset(pre, -1, sizeof(pre)); 62 bfs(); 63 64 //说明走不到这一点 65 if(dp[n-1][m-1] == -1) printf("God please help our poor hero. "); 66 else 67 { 68 printf("It takes %d seconds to reach the target position," 69 " let me show you the way. ", dp[n-1][m-1]); 70 t = 1; 71 Print(n - 1,m - 1); //打印路径。 72 } 73 printf("FINISH "); 74 } 75 return 0; 76 }