Dungeon Master(BFS)

题意：输出从S->E的最少时间，即最少步数。
BFS搜索六个方向。
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 using namespace std;
 5 int e_x,e_y,e_z;
 6 int n,row,col,vis[32][32][32];
 7 char map[32][32][32];
 8 int dir[6][3] = {{0,0,1},{0,0,-1},{0,-1,0},{0,1,0},{1,0,0},{-1,0,0}};
 9 struct node
10 {
11     int x;
12     int y;
13     int z;
14     int step;
15 } t,g;
16 int bfs(int x,int y,int z)
17 {
18     queue<node>q;
19     memset(vis,0,sizeof(vis));
20     t.step = 0;
21     t.x = x;
22     t.y = y;
23     t.z = z;
24     q.push(t);
25     vis[x][y][z] = 1;
26     while(!q.empty())
27     {
28         t = q.front();
29         q.pop();
30         if (t.x==e_x && t.y==e_y && t.z==e_z)
31         {
32             return t.step;
33         }
34         for (int i = 0; i < 6; i ++)
35         {
36             x = t.x +dir[i][0];
37             y = t.y+dir[i][1];
38             z = t.z +dir[i][2];
39             if (map[x][y][z]!='#'&&!vis[x][y][z])
40             {
41                 g.x = x;
42                 g.y = y;
43                 g.z = z;
44                 g.step = t.step+1;
45                 q.push(g);
46                 vis[x][y][z] = 1;
47             }
48         }
49 
50     }
51     return 0;
52 }
53 int main()
54 {
55 
56     char s[1010];
57     while(~scanf("%d%d%d",&n,&row,&col))
58     {
59         int i,j,k;
60         int s_x,s_y,s_z;
61         if (n==0&&row==0&&col==0)
62             break;
63         memset(map,'#',sizeof(map));
64         for (i = 0; i < n; i ++)
65         {
66             for (j = 0; j < row; j ++)
67             {
68                 scanf("%s",s);
69 
70                 for (k = 0 ; k < col; k ++)
71                 {
72 
73                     if (s[k]=='S')
74                     {
75                         s_x = j+1;
76                         s_y = k+1;
77                         s_z = i+1;
78                     }
79                     if (s[k]=='E')
80                     {
81                         e_x = j+1;
82                         e_y = k+1;
83                         e_z = i+1;
84                     }
85                     map[j+1][k+1][i+1] = s[k];
86                 }
87             }
88             getchar();
89         }
90         int ans = bfs(s_x,s_y,s_z);
91         if (ans)
92             printf("Escaped in %d minute(s).
",ans);
93         else
94             printf("Trapped!
");
95 
96     }
97     return 0;
98 }
View Code