POJ 2251 Dungeon Master(三维BFS)

题目大意：一个三维的牢房地图，有可以往上下前后左右六个方向移动，给你起点和出口，如果能从牢房出去，就输出所用时间。

解题思路：三维BFS，跟二维其实没什么区别，就是在原来方向上多了向上和向下两个方向，其他都差不多。

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 const int N=35;
 6 
 7 int n,m,h,ans;
 8 int d[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};//三维,相比于二维bfs仅多了向上和向下两个方向  
 9 char map[N][N][N];
10 int vis[N][N][N];
11 
12 struct node{
13     int x,y,z,step;
14 }pre,now;
15 
16 void bfs(int x,int y,int z){
17     queue<node>q;
18     now.x=x;
19     now.y=y;
20     now.z=z;
21     now.step=0;
22     q.push(now);
23     while(!q.empty()){
24         pre=q.front();
25         q.pop();
26         for(int i=0;i<6;i++){
27             int xx=pre.x+d[i][0];
28             int yy=pre.y+d[i][1];
29             int zz=pre.z+d[i][2];
30             if(xx<1||yy<1||zz<1||xx>n||yy>m||zz>h)
31                 continue;
32             if(vis[xx][yy][zz]||map[xx][yy][zz]=='#')
33                 continue;
34             if(map[xx][yy][zz]=='E'){
35                 ans=pre.step+1;
36                 return;
37             }
38             now.x=xx;
39             now.y=yy;
40             now.z=zz;
41             now.step=pre.step+1;
42             vis[xx][yy][zz]=1; 
43             q.push(now);
44         }
45     }
46     return;
47 }
48 
49 int main(){
50     while(~scanf("%d%d%d",&h,&n,&m)&&(h||n||m)){
51         memset(vis,0,sizeof(vis));
52         int sx,sy,sz;
53         for(int k=1;k<=h;k++){
54             if(k!=1)
55             getchar();
56             for(int i=1;i<=n;i++){
57                 getchar();
58                 for(int j=1;j<=m;j++){
59                     scanf("%c",&map[i][j][k]);
60                     if(map[i][j][k]=='S'){
61                         sx=i;sy=j;sz=k;
62                     }
63                 }
64             }
65         }    
66         ans=0;
67         bfs(sx,sy,sz);
68         if(ans)
69             printf("Escaped in %d minute(s).
",ans);
70         else
71             puts("Trapped!");
72     }
73 }