POJ 2252 Dungeon Master 三维水bfs

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 using namespace std;
 5 
 6 char maze[60][60][60];
 7 bool vis[60][60][60];
 8 int dir[6][3] = {{0,0,1}, {0,1,0}, {1,0,0}, {0,0,-1}, {0,-1,0}, {-1,0,0}};
 9 
10 struct Point
11 {
12     int x, y, z, step;
13 };
14 
15 struct Point start;
16 
17 queue<struct Point>q;
18 void bfs()
19 {
20     while(!q.empty())q.pop();
21     memset(vis, 0, sizeof(vis));
22     q.push(start);
23     vis[start.x][start.y][start.z] = 1;
24     while(!q.empty())
25     {
26         struct Point u = q.front();
27         q.pop();
28         if(maze[u.x][u.y][u.z] == 'E')
29         {
30             printf("Escaped in %d minute(s).
", u.step);
31             return;
32         }
33         for(int d = 0; d < 6; d++)
34         {
35             int nx = u.x + dir[d][0];
36             int ny = u.y + dir[d][1];
37             int nz = u.z + dir[d][2];
38             if(maze[nx][ny][nz] != '#' && maze[nx][ny][nz] != 0 && !vis[nx][ny][nz])
39             {
40                 q.push((struct Point){nx, ny, nz, u.step+1});
41                 vis[nx][ny][nz] = 1;
42             }
43         }
44     }
45     printf("Trapped!
");
46 }
47 
48 int main()
49 {
50     int a, b, c;
51     while(scanf("%d %d %d", &a, &b, &c) != EOF)
52     {
53         if(a == 0 && b == 0 && c == 0)break;
54         memset(maze, 0, sizeof(maze));
55         for(int i = 1; i <= a; i++)
56         {
57             for(int j = 1; j <= b; j++)
58             {
59                 scanf("%s", &maze[i][j][1]);
60                 for(int k = 1; k <= c; k++)
61                 {
62                     if(maze[i][j][k] == 'S')
63                         start = (struct Point){i, j, k, 0};
64                 }
65             }
66         }
67         bfs();
68     }
69     return 0;
70 }
View Code