POJ 2251 Dungeon Master（地牢大师）三维广搜

曾经终败给现在 2022-08-09 01:59 181阅读 0赞

题目链接：  
\[POJ 2251\] ([http://poj.org/problem?id=2251][http_poj.org_problem_id_2251])  
题目描述：  
Dungeon Master  
Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 21644 Accepted: 8419  
Description

You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

Is an escape possible? If yes, how long will it take?  
Input

The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).  
L is the number of levels making up the dungeon.  
R and C are the number of rows and columns making up the plan of each level.  
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a ‘\#’ and empty cells are represented by a ‘.’. Your starting position is indicated by ‘S’ and the exit by the letter ‘E’. There’s a single blank line after each level. Input is terminated by three zeroes for L, R and C.  
Output

Each maze generates one line of output. If it is possible to reach the exit, print a line of the form  
Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape.  
If it is not possible to escape, print the line  
Trapped!  
Sample Input

3 4 5  
S….  
.\#\#\#.  
.\#\#..

### . ###

#### \# ####

## . ##

## … ##

#### \# ####

# . #

#### E ####

1 3 3  
S\#\#

# E #

## \# ##

0 0 0  
Sample Output

Escaped in 11 minute(s).  
Trapped!  
Source

Ulm Local 1997  
言简意赅：  
此题为一道三维广搜的题目，分前后左右和上下六个方向，所以要用一个6\*3的数组来存放方向，并借助利用队列先进后出的特点来实现广搜，不能越界，不能走石块，在可以到达的地方进行操作，并记录步数，最后做好标记即可。  
代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    
    using namespace std;
    
    int L,R,C;
    char map[35][35][35];//用来存放输入的地牢迷宫图
    int vis[35][35][35];//用来标记是否走过的数组
    int sx,sy,sz,ex,ey,ez;//用于记录起点和终点的下标，注意是三维的
    int to[6][3]= {
       {
       0,0,1},{
       0,0,-1},{
       0,1,0},{
       0,-1,0},{
       1,0,0},{-1,0,0}};//上下前后左右六个方向
    
    struct node
    {
        int x,y,z,step;
    };
    int check(int x,int y,int z)//走之前要先判断一下，“1”表示此路不通，“0”表示可以通过
    {
        if(x<0||y<0||z<0||x>=L||y>=R||z>=C)//用于判断是否出界
            return 1;
        else if(map[x][y][z]=='#')//绝对不能走石块哟~
            return 1;
        else if(vis[x][y][z])//要是曾经走过也不行哟~
            return 1;
        return 0;
    }
    int bfs()
    {
        int i;
        node a,next;
        queue<node> Q;
        a.x=sx;
        a.y=sy;
        a.z=sz;
        a.step=0;
        vis[sx][sy][sz]=1;
        Q.push(a);//入队
        while(!Q.empty())
        {
            a=Q.front();//用a节点从队列里读出数据
            Q.pop();//删除即可
            if(a.x==ex&&a.y==ey&&a.z==ez)
            {
                return a.step;
            }
            for(i=0; i<=6; i++)
            {
                next=a;
                next.x=a.x+to[i][0];
                next.y=a.y+to[i][1];
                next.z=a.z+to[i][2];
                if(check(next.x,next.y,next.z))
                    continue;
                vis[next.x][next.y][next.z]=1;
                next.step=a.step+1;
                Q.push(next);//入队
            }
        }
        return 0;
    }
    
    int main()
    {
        while(scanf("%d%d%d",&L,&R,&C)!=EOF)
        {
            if(L==0&&R==0&&C==0)
                break;
            for(int i=0; i<L; i++)
            {
                for(int j=0; j<R; j++)
                {
                    scanf("%s",map[i][j]);
                    for(int r=0; r<C; r++)
                    {
                        if(map[i][j][r]=='S')
                        {
                            sx=i;
                            sy=j;
                            sz=r;
                        }
                        else if(map[i][j][r]=='E')
                        {
                            ex=i;
                            ey=j;
                            ez=r;
                        }
                    }
                }
            }
            memset(vis,0,sizeof(vis));
            int ans;
            ans=bfs();
            if(ans)
                printf("Escaped in %d minute(s).\n",ans);
            else printf("Trapped!\n");
        }
        return 0;
    }

[http_poj.org_problem_id_2251]: http://poj.org/problem?id=2251