http://poj.org/problem?id=2251
題意 ： 就是迷宮升級版，從以前的一個矩陣也就是一層，變為現在的L層，" . "是可以走，但是“#”不可以走，從S走到E，求最短的路徑，若是找不到就輸出“Trapped！”，每一層的同一個位置若都是" . "是可以直接走的，換句話說，map[1][j][k]與map[2][j][k]若都是" . ",是可以從map[1][j][k]走到map[2][j][k]的
思路 ： 求最短路徑，用BFS ,這個題比較搞，分類在DFS里，但用DFS會超時啊，所以倒是欺騙了不少童鞋，這個題我沒寫不出來，會神說用3維的東南西北上下，六個方向進行搜索即可，好吧，好麻煩
#include<cstdio> #include<iostream> #include<queue> #include<cstring> using namespace std ; const int maxn = 70 ; char map[maxn][maxn][maxn] ; int vis[maxn][maxn][maxn] ; struct node {int x,y,z;int step ; }ch,sh ; int floor,row,col ; int s[7][4] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}} ; //存的方向，分別為上，下，東，西，北，南代表6個方向，里邊的3個元素分別為z軸，x軸，y軸 int ex,ey,ez ; int stepp,zz,xx,yy; int sx,sy,sz; void bfs(int x,int y,int z) {queue<node>Q;ch.x = x ;ch.y = y ;ch.z = z ;ch.step = 0 ;//初始化Q.push(ch) ;//入隊列vis[z][x][y] = 1 ;//標記為1while(!Q.empty()){sh = Q.front() ;Q.pop();if(sh.x == ex&&sh.y == ey&&sh.z == ez){stepp = sh.step ;//如果到了E點，就把步數保存下來，并返回return ;}for(int i = 0 ; i < 6 ; i++)//東南西北上下六個方向進行搜索 {zz = sh.z+s[i][0] ;xx = sh.x+s[i][1] ;yy = sh.y+s[i][2] ;if(zz>=0&&xx>=0&&yy>=0&&zz<floor&&xx<row&&yy<col&&map[zz][xx][yy]!= '#'&&!vis[zz][xx][yy]){//找到沒有出邊界的，不是'#'的，并且未被訪問過的就進行入隊操作ch.x = xx ;ch.y = yy ;ch.z = zz ;ch.step = sh.step+1;Q.push(ch) ;vis[zz][xx][yy] = 1 ;//標記這個點為已訪問 }}} } int main() {while(~scanf("%d %d %d",&floor,&row,&col)){if(floor == 0&& row == 0&&col == 0)break ;stepp = 0 ;memset(vis,0,sizeof(vis)) ;for(int i = 0 ; i < floor ; i++){for(int j = 0 ; j < row ; j++){cin>>map[i][j] ;getchar();for(int k = 0 ; k < col ; k++){if(map[i][j][k] == 'S')//把S點的坐標保存下來 {sz = i ;sx = j ;sy = k ;}if(map[i][j][k] == 'E'){ez = i ;ex = j ;ey = k ;}}}}bfs(sx,sy,sz) ;if(stepp == 0)cout<<"Trapped!"<<endl ;elsecout<<"Escaped in "<<stepp<<" minute(s)."<<endl ;}return 0 ; }
?
