BFS解決POJ 2251
Description
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.
Is an escape possible? If yes, how long will it take?
Is an escape possible? If yes, how long will it take?
Input
The input consists of a
number of dungeons. Each dungeon description starts with a line containing three
integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Each maze generates one
line of output. If it is possible to reach the exit, print a line of the form
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
Sample Output
Escaped in 11 minute(s).
Trapped!
此題目是三維的迷宮問題，要想解決本題，首先要有二維的BFS相關知識，
有了這個之后，還是不行的，還要搞清楚行走的坐標的表示。
一開始，我本以為要開一個三維的數組來表示走法，但是，用二維的才是正確的。
如何正確，我將在代碼中做出詳細的說明。另外的一些注意事項，也會在代碼中
做出詳細的解釋。
View Code
#include<iostream> #include<string.h> using namespace std; int level, row, col, i, j, k, sx, sy, sz, tx, ty, tz; char map[35][35][35]; int used[35][35][35]; int step[35][35][35]; int direction[6][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}}; ///好了，現在來好好解釋一下direction[][]數組，也就是走法。一共有6種走法，上下左右前后。故要開direction[6][]; ///為何要開direction[][3]呢？也就是這個3該如何解釋呢？學過幾何的人都知道x,y,z的空間坐標軸。這就是3的來歷。 ///拿｛0，0，1｝來說，表示x=0, y=0, z=1,很明顯了，這種走法表示的是向上走了。其它的類似，不再說了。 ///同樣的，direction[4][2]中的2，也是同樣的道理。只不過沒有了z坐標。 struct point { int x,y,z; }queue[30000]; int BFS(int sz, int sx, int sy) { used[sz][sx][sy] = 1; int head = 0, tail = 0; queue[head].z = sz; queue[head].x = sx; queue[head].y = sy; head++; while(tail<head) { point t1 = queue[tail]; tail++; int m; for(m=0; m<6; m++) { point t2; t2.z = t1.z+direction[m][2]; t2.x = t1.x+direction[m][0]; t2.y = t1.y+direction[m][1]; if(t2.z>=0 && t2.z<level && t2.x>=0 && t2.x<row && t2.y>=0 && t2.y<col && used[t2.z][t2.x][t2.y]==0) { if(map[t2.z][t2.x][t2.y]=='.') { step[t2.z][t2.x][t2.y] = step[t1.z][t1.x][t1.y]+1; used[t2.z][t2.x][t2.y] = 1; queue[head] = t2; head++; } else if(map[t2.z][t2.x][t2.y]=='E') return (step[t1.z][t1.x][t1.y]+1); } } } return -1; } int main() { while(cin>>level>>row>>col && (level+row+col)) { memset(used, 0, sizeof(used)); memset(step, 0, sizeof(step)); for(i=0; i<level; i++) for(j=0; j<row; j++) for(k=0; k<col; k++) { cin>>map[i][j][k]; if(map[i][j][k]=='S') ///一定要注意這里的map[i][j][k]中的三個參數i, j, k. /// i 對應層數，也就是z軸 /// j 對應行數，也就是x軸 /// z 對應列數，也就是y軸 ///因此，在下面的運算中要一一對應起來的。否則將會出錯的。 { sx = j; sy = k; sz = i; } } int result = BFS(sz, sx, sy); if( result==-1 ) cout<<"Trapped!"<<endl; else cout<<"Escaped in "<<result<<" minute(s)."<<endl; } }
posted on 2011-09-23 22:34 More study needed. 閱讀(186) 評論(0) 收藏 舉報
浙公網安備 33010602011771號