Dungeon Master

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<queue>
 6 #include<algorithm>
 7 #define MAXN 40
 8 using namespace std;
 9 
10 char map[MAXN][MAXN][MAXN];
11 bool vis[MAXN][MAXN][MAXN];
12 int s[][10]= {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
13 int ex,ey,ez,sx,sy,sz,zz,yy,xx,l,r,c,k;
14 struct node
15 {
16     int x,y,z;
17     int step;
18 }st,st1;
19 
20 void bfs(int x,int y,int z)
21 {
22     memset(vis,false,sizeof(vis));
23     queue<node>q;
24     st.x=x;
25     st.y=y;
26     st.z=z;
27     st.step=0;
28     q.push(st);
29     vis[z][x][y]=true;
30     while(!q.empty())
31     {
32         st1=q.front();
33         q.pop();
34         if(st1.x==ex&&st1.y==ey&&st1.z==ez) {k=st1.step;return;}
35         for(int i=0; i<6; i++)
36         {
37             zz=st1.z+s[i][0];
38             xx=st1.x+s[i][1];
39             yy=st1.y+s[i][2];
40             if((zz>=0&&xx>=0&&yy>=0&&zz<l&&xx<r&&yy<c)&&map[zz][xx][yy]!='#'&&!vis[zz][xx][yy])
41             {
42                 st.x=xx;
43                 st.y=yy;
44                 st.z=zz;
45                 st.step=st1.step+1;
46                 q.push(st);
47                 vis[zz][xx][yy]=true;
48             }
49         }
50     }
51 }
52 int main()
53 {
54     while(scanf("%d%d%d",&l,&r,&c)!=EOF)
55     {
56         k=0;
57         if(l==0&&r==0&&c==0) break;
58         for(int i=0; i<l; i++)
59         {
60             for(int j=0; j<r; j++)
61             {
62                 scanf("%s",map[i][j]);
63                 getchar();
64                 for(int k=0; k<c; k++)
65                 {
66                     if(map[i][j][k]=='S')
67                     {
68                         sz=i;
69                         sx=j;
70                         sy=k;
71                     }
72                     else if(map[i][j][k]=='E')
73                     {
74                         ez=i;
75                         ex=j;
76                         ey=k;
77                     }
78                 }
79             }
80             getchar();
81         }
82         bfs(sx,sy,sz);
83         if(k==0)
84             printf("Trapped!
");
85         else
86             printf("Escaped in %d minute(s).
",k);
87     }
88     //system("pause");
89     return 0;
90 }
View Code