題干：

The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess. Now he gets into feng5166's castle. The castle is a large labyrinth. To make the problem simply, we assume the labyrinth is a N*M two-dimensional array which left-top corner is (0,0) and right-bottom corner is (N-1,M-1). Ignatius enters at (0,0), and the door to feng5166's room is at (N-1,M-1), that is our target. There are some monsters in the castle, if Ignatius meet them, he has to kill them. Here is some rules:?

1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).?
2.The array is marked with some characters and numbers. We define them like this:?
. : The place where Ignatius can walk on.?
X : The place is a trap, Ignatius should not walk on it.?
n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.?

Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.?

Input

The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole labyrinth. The input is terminated by the end of file. More details in the Sample Input.?

Output

For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds), and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output.?

Sample Input

5 6 .XX.1. ..X.2. 2...X. ...XX. XXXXX. 5 6 .XX.1. ..X.2. 2...X. ...XX. XXXXX1 5 6 .XX... ..XX1. 2...X. ...XX. XXXXX.

Sample Output

It takes 13 seconds to reach the target position, let me show you the way. 1s:(0,0)->(1,0) 2s:(1,0)->(1,1) 3s:(1,1)->(2,1) 4s:(2,1)->(2,2) 5s:(2,2)->(2,3) 6s:(2,3)->(1,3) 7s:(1,3)->(1,4) 8s:FIGHT AT (1,4) 9s:FIGHT AT (1,4) 10s:(1,4)->(1,5) 11s:(1,5)->(2,5) 12s:(2,5)->(3,5) 13s:(3,5)->(4,5) FINISH It takes 14 seconds to reach the target position, let me show you the way. 1s:(0,0)->(1,0) 2s:(1,0)->(1,1) 3s:(1,1)->(2,1) 4s:(2,1)->(2,2) 5s:(2,2)->(2,3) 6s:(2,3)->(1,3) 7s:(1,3)->(1,4) 8s:FIGHT AT (1,4) 9s:FIGHT AT (1,4) 10s:(1,4)->(1,5) 11s:(1,5)->(2,5) 12s:(2,5)->(3,5) 13s:(3,5)->(4,5) 14s:FIGHT AT (4,5) FINISH God please help our poor hero. FINISH

解題報告：

? ? 其實記錄路徑的方法有很多，這里用的兩個二維數組是其中一種，然而用棧表示其實也是大材小用了，只要dfs的時候多傳兩個參數就可以解決了 。還有一種方法就是定義一個結構體，并且可以順便結構體中int x,y;char c;（或者int c）? 這樣可以順便把這個地方的字符是‘ . ’? 還是0-9中的數字 可以表示出來了。

? ? 其實第一遍寫還是很容易錯的。但是比較良心的就是，特殊情況樣例都給的比較清楚了，比如在(n,m)那個點有怪物的情況。這樣我們依據樣例就可以修正代碼了。

AC代碼：（這代碼我保證我都不敢再看第二遍了。。。）

#include<bits/stdc++.h>using namespace std; int n,m,curtime; bool vis[105][105]; char maze[105][105]; int pathx[105][105]; int pathy[105][105]; int nx[4] = {0,1,0,-1}; int ny[4] = {1,0,-1,0}; stack<int> xx,yy; struct Node {int x,y;int time;Node(){}Node(int x,int y,int time):x(x),y(y),time(time){}bool operator < (const Node b) const{return time > b.time;} }; int bfs(int sx,int sy) {memset(vis,0,sizeof vis);priority_queue<Node> pq;pq.push(Node(sx,sy,0));while(!pq.empty()) {Node cur = pq.top();pq.pop();int tx,ty;if(cur.x == n && cur.y == m) return cur.time;for(int k = 0; k<4; k++) {tx = cur.x + nx[k];ty = cur.y + ny[k];if(tx < 1 || tx > n || ty < 1 || ty > m) continue;if(maze[tx][ty] == 'X' || vis[tx][ty] == 1) continue;vis[tx][ty]=1;if(maze[tx][ty] == '.') {pq.push(Node(tx,ty,cur.time + 1));pathx[tx][ty] = cur.x;pathy[tx][ty] = cur.y;}else {pq.push(Node(tx,ty,cur.time + 1 + maze[tx][ty] - '0'));pathx[tx][ty] = cur.x;pathy[tx][ty] = cur.y;}}}return -1; } void dfs(int x,int y) {if(x == 1 && y == 1) {printf("%ds:(0,0)->(%d,%d)\n",++curtime,xx.top()-1,yy.top()-1);xx.pop();yy.pop();return ;}dfs(pathx[x][y],pathy[x][y]);if(x == n && y == m) {if(maze[x][y]!='.'){int all = maze[x][y] - '0';while(all--)printf("%ds:FIGHT AT (%d,%d)\n",++curtime,x-1,y-1);}return ;}if(maze[x][y] == '.') {printf("%ds:(%d,%d)->(%d,%d)\n",++curtime,x-1,y-1,xx.top()-1,yy.top()-1);xx.pop();yy.pop();}else {int all = maze[x][y] - '0';while(all--)printf("%ds:FIGHT AT (%d,%d)\n",++curtime,x-1,y-1);printf("%ds:(%d,%d)->(%d,%d)\n",++curtime,x-1,y-1,xx.top()-1,yy.top()-1);xx.pop();yy.pop();} }int main() {while(cin>>n>>m) {while(xx.size()) xx.pop();while(yy.size()) yy.pop();for(int i = 1; i<=n; i++) {scanf("%s",maze[i]+1);}int ans = bfs(1,1);if(ans == -1) {printf("God please help our poor hero.\nFINISH\n");continue;}printf("It takes %d seconds to reach the target position, let me show you the way.\n",ans);curtime = 0;int i=n,j=m;while(i!=1 || j!=1) {//不能是&& ！！！或者 while(!(i==1&&j==1)) xx.push(i);yy.push(j);//所以path用結構體存多好。。。 int tmpx = pathx[i][j];int tmpy = pathy[i][j];i=tmpx,j=tmpy;} // while(xx.size()){ // printf("%d ",xx.top());xx.pop(); // } // printf("\n"); // while(yy.size()){ // printf("%d ",yy.top());yy.pop(); // }dfs(n,m);printf("FINISH\n");}return 0 ; } //23:31 - 24:10

總結：

? 寫記錄路徑的時候的幾個錯誤點：

? ?第一：剛開始沒有寫56行左右的那個if(x==n && y==m)? ? ?后果：后來發現如果不寫這個，也進入下面的printf，那么就會棧空的情況下xx.top()，肯定是會炸的。

? ?第二 ：剛開始改的時候直接if(x==n && y==m)? return;? ?但是發現第二個樣例不對，因為我的curtime還沒到我的ans，所以我還需要判斷是否在x==n && y==m這一點打架了，即這一點是否有怪物。而且還不能直接讓他進入下面的else，因為我并不想讓他輸出printf("%ds:(%d,%d)->(%d,%d)\n",++curtime,x-1,y-1,xx.top()-1,yy.top()-1);這一句。所以無奈只能在if(x==n && y==m)? return; 這里面做判斷輸出、

其實還有一種辦法就是把FIGNT那個輸出跟在“->”那種輸出的后面，而不是先“->”輸出這個 ，再輸出FIGNT那個。類似于這種處理

int flag=bfs();if(flag!=-1){printf("It takes %d seconds to reach the target position, let me show you the way.\n",flag);sec=1,x=y=0;while(sec!=flag+1){printf("%ds:(%d,%d)->(%d,%d)\n",sec++,x,y,map[x][y].nx,map[x][y].ny);for(i=0;i<fight[map[x][y].nx][map[x][y].ny];i++)printf("%ds:FIGHT AT (%d,%d)\n",sec++,map[x][y].nx,map[x][y].ny);tx=map[x][y].nx;ty=map[x][y].ny;x=tx;y=ty;} } elseprintf("God please help our poor hero.\n");printf("FINISH\n");

?

總結

以上是生活随笔為你收集整理的【HDU - 1026 】Ignatius and the Princess I （bfs + 记录路径）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。