【POJ2251】Dungeon Master

problem

solution

codes

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n, m, o, a[40][40][40], vis[40][40][40];
int sx, sy, sz, ex, ey, ez, ans;
const int dx[] = {1,-1,0,0,0,0};
const int dy[] = {0,0,1,-1,0,0};
const int dz[] = {0,0,0,0,1,-1};
struct node{
    int x, y, z, step;
    node(int x = 0, int y = 0, int z = 0, int step = 0):x(x),y(y),z(z),step(step){}
};
void bfs(){
    queue<node>q;
    q.push(node(sx,sy,sz,0));
    a[sx][sy][sz] = 1;
    //vis[sx][sy][sz] = 1;
    while(!q.empty()){
        node t = q.front();  q.pop();
        if(t.x==ex && t.y==ey && t.z==ez){
            ans = t.step;
        }
        for(int i = 0; i < 6; i++){
            int nx = t.x+dx[i], ny = t.y+dy[i], nz = t.z+dz[i];
            if(nx>0 && nx<=n && ny>0 && ny<=m && nz>0 && nz<=o && !a[nx][ny][nz]){
                q.push(node(nx,ny,nz,t.step+1));
                a[nx][ny][nz]  = 1;
                //vis[nx][ny][nz] = 1;
            }
        }
    }
}
int main(){
    while(cin>>n>>m>>o &&n){
        ans = 0;
        memset(a,0,sizeof(a));
        //memset(vis,0,sizeof(vis));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                for(int k = 1; k <= o; k++){
                    char ch;  cin>>ch;
                    if(ch == '#')a[i][j][k] = 1;
                    if(ch == 'S'){ sx = i; sy = j; sz = k;}
                    if(ch == 'E'){ ex = i; ey = j; ez = k;}
                }
            }
        }
        bfs();
        if(ans)cout<<"Escaped in "<<ans<<" minute(s).\n";
        else cout<<"Trapped!\n";
    }
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80461098