POJ 2251 Dungeon Master(BFS)

秒速五厘米 2022-05-17 21:58 95阅读 0赞

题意：有一个三维的迷宫，可以上下左右前后六种方式行走，每移动一格需要耗费一分钟，\# 代表墙（无法到达的地方），S代表起点，E代表终点，问你能否从起点到达终点，如果能就输出耗费时间，不能则输出Trapped!

分析：BFS裸题，只不过现在是在三维里面，可以走六个方向。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define maxn 35
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    int l,r,c;
    
    char maze[maxn][maxn][maxn];
    int vis[maxn][maxn][maxn];
    int dir[6][3]={
       {1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
    
    struct node
    {
        int x,y,z,t;
    };
    node vs,ed;
    
    queue<node>q;
    
    void init()
    {
        while(!q.empty()) q.pop();
        Clear(vis);
    }
    
    bool check(int x,int y,int z)
    {
        if(x<0||x>=l||y<0||y>=r||z<0||z>=c) return false;
        if(maze[x][y][z]=='#'||vis[x][y][z]) return false;
        return true;
    }
    
    int BFS()
    {
        node temp;
        q.push(vs);
        while(!q.empty()){
            node now = q.front();
            q.pop();
            if(now.x==ed.x&&now.y==ed.y&&now.z==ed.z) return now.t;
            for(int i=0;i<6;i++)
            {
                temp.x=now.x+dir[i][0];
                temp.y=now.y+dir[i][1];
                temp.z=now.z+dir[i][2];
                if(check(temp.x,temp.y,temp.z))
                {
                    vis[temp.x][temp.y][temp.z]=1;
                    temp.t=now.t+1;
                    q.push(temp);
                }
            }
        }
        return -1;
    }
    
    int main()
    {
        while(scanf("%d%d%d",&l,&r,&c)==3&&l&&r&&c)
        {
            init();
            for(int i=0;i<l;i++)
            {
                for(int j=0;j<r;j++)
                {
                    scanf("%s",maze[i][j]);
                    for(int k=0;k<c;k++)
                    {
                        if(maze[i][j][k]=='S') vs.x=i,vs.y=j,vs.z=k,vs.t=0;
                        if(maze[i][j][k]=='E') ed.x=i,ed.y=j,ed.z=k;
                    }
                }
            }
            int ans = BFS();
            if(ans==-1) printf("Trapped!\n");
            else printf("Escaped in %d minute(s).\n",ans);
        }
        return 0;
    }