# poj-2251-Dungeon Master（三维 bfs 最短路）

## 2 Input - 输入

L 表示空间的高度。R 和 C 分别表示每层空间的行与列的大小。

## 3 Output - 输出

Escaped in x minute(s).

x 为最短脱离时间。

Trapped!

## 4 Sample Input - 输入样例

``````3 4 5
S....
.###.
.##..
###.#

#####
##.##
##...

#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
``````

## 5 Sample Output - 输出样例

``````Escaped in 11 minute(s).
Trapped!
``````

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 `````` ``````#include #include #include #include #include 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 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

Buy me a coffee~