題目：

你被困在一個(gè)3D地牢中且繼續(xù)尋找最短路徑逃生！地牢由立方體單位構(gòu)成，立方體中不定會(huì)充滿巖石。向上下前后左右移動(dòng)一個(gè)單位需要一分鐘。你不能對(duì)角線移動(dòng)并且迷宮四周堅(jiān)石環(huán)繞。

是否存在逃出生天的可能性？如果存在，則需要多少時(shí)間？
Input - 輸入
　　輸入第一行是一個(gè)數(shù)表示地牢的數(shù)量。
　　每個(gè)地牢的描述的第一行為L(zhǎng)，R和C（皆不超過(guò)30）。
　　L表示地牢的層數(shù)。
　　R和C分別表示每層地牢的行與列的大小。

隨后L層地牢，每層R行，每行C個(gè)字符。
　　每個(gè)字符表示地牢的一個(gè)單元。’#‘表示巖石單元，’.‘表示空白單元。你的起始位置在’S’，出口為’E’。
　　每層地牢后都有一個(gè)空行。L，R和C均為0時(shí)輸入結(jié)束。
Output - 輸出
　　每個(gè)迷宮對(duì)應(yīng)一行輸出。
　　如果可以逃生，則輸出如下
Escaped in x minute(s).
　　x為最短脫離時(shí)間。

如果無(wú)法逃生，則輸出如下
Trapped!
Sample Input - 輸入樣例
3 4 5
S…
.###.
.##…
###.#

##.##
##…

#.###
####E

1 3 3
S##
#E#

0 0 0
Sample Output - 輸出樣例
Escaped in 11 minute(s).
Trapped!

分析與解答

有圖的這種搜索，先把圖存到數(shù)組里，三個(gè)方向移動(dòng)，每個(gè)方向可以往前往后走，就寫一個(gè)方向數(shù)組，（3*2）*3的數(shù)組
然后把起點(diǎn)先push到queue里，之后把每個(gè)移動(dòng)的可能情況都考慮到，每移動(dòng)一次，如果滿足這個(gè)坐標(biāo)沒出現(xiàn)過(guò)，這個(gè)坐標(biāo)沒越界，這個(gè)坐標(biāo)是可以移動(dòng)的，就push到queue里，然后標(biāo)記數(shù)組標(biāo)記移動(dòng)到的坐標(biāo)，并將step增加
這個(gè)層都放到queue之后，下一次循環(huán)開始還是先取出第一個(gè)數(shù)，然后繼續(xù)

#include <iostream> #include <stdio.h> #include <string.h> #include <queue> #include <algorithm> using namespace std;char map[35][35][35]; int vis[35][35][35]; int k,n,m,sx,sy,sz,ex,ey,ez; int to[6][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};struct node {int x,y,z,step; };int check(int x,int y,int z) {if(x<0 || y<0 || z<0 || x>=k || y>=n || z>=m)return 1;else if(map[x][y][z] == '#')return 1;else if(vis[x][y][z])return 1;return 0; }int bfs() {int i;node a,next;queue<node> Q;a.x = sx,a.y = sy,a.z = sz;a.step = 0;vis[sx][sy][sz] = 1;Q.push(a);while(!Q.empty()){a = Q.front();Q.pop();if(a.x == ex && a.y == ey && a.z == ez)return a.step;for(i = 0; i<6; i++){next = a;next.x = a.x+to[i][0];next.y = a.y+to[i][1];next.z = a.z+to[i][2];if(check(next.x,next.y,next.z))continue;vis[next.x][next.y][next.z] = 1;next.step = a.step+1;Q.push(next);}}return 0; }int main() {int i,j,r;while(scanf("%d%d%d",&k,&n,&m),n+m+k){for(i = 0; i<k; i++){for(j = 0; j<n; j++){scanf("%s",map[i][j]);for(r = 0; r<m; r++){if(map[i][j][r] == 'S'){sx = i,sy = j,sz = r;}else if(map[i][j][r] == 'E'){ex = i,ey = j,ez = r;}}}}memset(vis,0,sizeof(vis));int ans;ans = bfs();if(ans)printf("Escaped in %d minute(s).\n",ans);elseprintf("Trapped!\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的（BFS）Dungeon Master（poj2251）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。