Dungeon Master POJ2251

发表于 更新于 分类于 ， 阅读次数： 本文字数： 336 阅读时长 ≈ 1 分钟

BFS+三维，一直WA找不到问题，后来发现是没有初始化（菜

问题链接，AC代码：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<queue>
#include <stdio.h>
#include <string.h>

using namespace std;

#define N 32

struct node
{
    int x,y,z,time;
};


int sx,sy,sz;//start
int ex,ey,ez;//end

int mp [N][N][N]={0};
int vis[N][N][N]={0};

int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};

int L,R,C;//z,y,x

bool check(int x,int y,int z){
    if(x>=1 && x <=C && y>=1 && y<=R && z>=1 && z<=L && vis[x][y][z]==0 && mp[x][y][z])return true;
    return false;
}

int dfs(node s,node e){
    queue<node>q;
    q.push(s);

    while(!q.empty()){
        node fis=q.front();
        q.pop();
        node nw;

        for(int i=0;i<6;i++){
            nw.x=fis.x+dx[i];
            nw.y=fis.y+dy[i];
            nw.z=fis.z+dz[i];
            nw.time=fis.time+1;
            if(check(nw.x,nw.y,nw.z)){
                vis[nw.x][nw.y][nw.z]=1;
                q.push(nw);
                if( nw.x == e.x &&  nw.y == e.y && nw.z == e.z ){
                    return nw.time;
                }
            }
        }
    }
    return 0;
}

int main(){
    char ch;
    while(cin>>L>>R>>C){
        if(L==0&&R==0&&C==0)break;//stop

        memset(vis,0,sizeof(vis));
        memset(mp,0,sizeof(mp));//initialize

        for(int i=1;i<=L;i++)//z
        {
            for(int j=1;j<=R;j++)//y
            {
                for(int k=1;k<=C;k++)//x
                {
                    cin>>ch;
                    if(ch=='S')sx=k,sy=j,sz=i,mp[k][j][i]=1,vis[k][j][i]=1;
                    else if(ch=='E')ex=k,ey=j,ez=i,mp[k][j][i]=1;
                    else if(ch=='.')mp[k][j][i]=1;
                    else if(ch=='#')mp[k][j][i]=0;
                    else break;
                }
            }
        }//input

         node s,e;
         s.x=sx,s.y=sy,s.z=sz,s.time=0;
         e.x=ex,e.y=ey,e.z=ez;

        int ret=dfs(s,e);

        if(ret)cout<<"Escaped in "<<ret<<" minute(s).\n";
        else cout<<"Trapped!\n";
    }
    return 0;
}