POJ 2251 Dungeon Master(三维bfs)

时间:2021-05-28 16:25:13

简单题,熟悉下操作就可以完成。
出题率依然低下,得想办法加快了。
非人的恐惧追猎着沉默的发声者。
代码:

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int l,r,c;
char map[35][35][35];
struct node
{
    int x,y,z,step;
} q[35*35*35*100];
bool vis[35][35][35];
bool judge(node x)
{
    if(x.x>=0&&x.x<l&&x.y>=0&&x.y<r&&x.z>=0&&x.z<c&&!vis[x.x][x.y][x.z]&&(map[x.x][x.y][x.z]=='.'||map[x.x][x.y][x.z]=='E'))return 1;
    return 0;
}
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,0,0,-1,1};
int dz[]={0,0,-1,1,0,0};
int bfs(int sx,int sy,int sz)
{
    memset(vis,0,sizeof(vis));
    int front=0,rear=1;
    q[front].x=sx;
    q[front].y=sy;
    q[front].z=sz;
    q[front].step=0;
    //vis[sx][sy][sz]=1;
    /*这里注意SE可以相同的,别把自己的通路堵死。*/
    while(front<rear)
    {
        for(int i=0; i<6; i++)
        {
            node nxt = q[front];
            nxt.x+=dx[i];
            nxt.y+=dy[i];
            nxt.z+=dz[i];
            if(judge(nxt))
            {
                vis[nxt.x][nxt.y][nxt.z]=1;
                q[rear].x=nxt.x;
                q[rear].y=nxt.y;
                q[rear].z=nxt.z;
                q[rear++].step=nxt.step+1;
            }
            if(map[nxt.x][nxt.y][nxt.z]=='E')return nxt.step+1;
        }
        front++;
    }
    return -1;
}
int main()
{
    while(cin>>l>>r>>c)
    {
        if(l==0&&r==0&&c==0)return 0;
        int sx,sy,sz,ex,ey,ez;
        for(int i=0; i<l; i++)
            for(int j=0; j<r; j++)
                for(int k=0; k<c; k++)
                {
                    cin>>map[i][j][k];
                    if(map[i][j][k]=='S')
                    {
                        sx=i;
                        sy=j;
                        sz=k;
                    }
                }
                //cout<<sx<<" "<<sy<<" "<<sz<<" "<<ex<<" "<<ey<<" "<<ez<<endl;
                int ans=bfs(sx,sy,sz);
                if(ans!=-1)
                printf("Escaped in %d minute(s).\n",ans);
                else
                cout<<"Trapped!"<<endl;
    }
}