POJ 2251 Dungeon Master

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 const int maxn = 40;
 8 char map[maxn][maxn][maxn];
 9 int vis[maxn][maxn][maxn];
10 int k,n,m;
11 int dx[6] = {0,0,-1,1,0,0};
12 int dy[6] = {-1,1,0,0,0,0};
13 int dz[6] = {0,0,0,0,-1,1};
14 int ex,ey,ez;
15 int sx,sy,sz;
16 struct node{
17     int x,y,z;
18     int dep;
19 };
20 bool check(int x,int y,int z)
21 {
22     if(x >= 0 && x < k && y >= 0 && y < n && z >= 0 && z < m) return true;
23     else return false;
24 }
25 int bfs(int i,int j,int k)
26 {
27     node a,next;
28     queue<node> q;
29     vis[i][j][k] = 1;
30     a.x = i,a.y = j,a.z = k;
31     a.dep = 0;
32     q.push(a);
33     while(!q.empty())
34     {
35         a = q.front();q.pop();
36         if(a.x == ex && a.y == ey && a.z == ez) return a.dep;
37         for(int i = 0;i < 6;i++)
38         {
39             next = a;
40             next.x = a.x + dx[i];
41             next.y = a.y + dy[i];
42             next.z = a.z + dz[i];
43             if(check(next.x,next.y,next.z) && !vis[next.x][next.y][next.z] && map[next.x][next.y][next.z] != '#')
44             {
45                 next.dep = a.dep + 1;
46                 vis[next.x][next.y][next.z] = 1;
47                 q.push(next);
48             }
49         }
50     }
51     return 0;
52 }
53 int main()
54 {
55     while(~scanf("%d%d%d",&k,&n,&m) && (n||m||k))
56     {
57         for(int i = 0;i < k;i++)
58         {
59             for(int j = 0;j < n;j++)
60             {
61                 scanf("%s",map[i][j]);
62                 for(int k = 0;k < m;k++)
63                 {
64                     if(map[i][j][k] == 'S')
65                     {
66                         sx = i, sy = j,sz = k;
67                     }
68                     if(map[i][j][k] == 'E')
69                     {
70                         ex = i,ey = j,ez = k;
71                     }
72                 }
73             }
74         }
75         memset(vis,0,sizeof(vis));
76         int ans = bfs(sx,sy,sz);
77         if(ans)
78             printf("Escaped in %d minute(s).\n",ans);
79         else
80             printf("Trapped!\n");
81     }
82     return 0;
83 }