AcWing 1096. Detailed notes of Dungeon Master (3D BFS) code

Original link ：https://www.acwing.com/problem/content/1098/

subject ：

 

You are now trapped in a three-dimensional dungeon , We need to find the fastest way out ！

The dungeon consists of several unit cubes , Some of them do not contain rock obstacles and can pass directly through , Some contain rock obstacles that cannot be passed .

To the north , Southward , To the east , To the West , It takes one minute to move a unit up or down .

You can't move diagonally , The boundary of the maze is hard rock , You can't go beyond the boundary .

Excuse me, , Is it possible for you to escape ？

If possible , How long does it take? ？

Input format

Input contains multiple sets of test data .

The first row of each set of data contains three integers  L,R,C Each represents the number of dungeons , And the number of rows and columns in each dungeon .

Next is  L  individual  R  That's ok  C  The character matrix of the column , Used to indicate the specific condition of each dungeon .

Each character is used to describe the specific situation of a dungeon unit .

among , Cells filled with rock obstacles are used ”#” Express , Empty cells without obstacles use ”.” Express , Your starting position is ”S” Express , End with ”E” Express .

Each character matrix will contain a blank line .

When entering a behavior ”0 0 0” when , Indicates that the input is terminated .

Output format

Each group of data outputs a result , Each result takes up one line .

If you can escape the dungeon , The output ”Escaped in x minute(s).”, among X The shortest time required to escape .

If you can't escape the dungeon , The output ”Trapped!”.

Data range

1≤L,R,C≤100

sample input ：

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

sample output ：

Escaped in 11 minute(s).
Trapped!

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=110;
char mp[N][N][N];// Store maps 
int res[N][N][N];// Store the number of steps and mark 
int l,r,c;
int xs,ys,zs;// The starting point 
typedef struct {
    int x,y,z;
}k;
int bfs()
{
    // Three dimensional map , Six directions 
    int dx[6]={1,0,-1,0,0,0};
    int dy[6]={0,1,0,-1,0,0};
    int dz[6]={0,0,0,0,1,-1};
    queue<k>q;
    q.push({xs,ys,zs});// Read in start position 
    res[xs][ys][zs]=0;// The starting position distance is 0
    while(!q.empty())
    {
        auto w=q.front();// Take out the first point in the queue 
        q.pop();
        for(int i=0;i<6;i++)
        {
            int xx=w.x+dx[i];int yy=w.y+dy[i];int zz=w.z+dz[i];// Coordinates after offset 
            if(xx>=1&&xx<=l&&yy>=1&&yy<=r&&zz>=1&&zz<=c&&res[xx][yy][zz]==-1&&mp[xx][yy][zz]!='#')// Boundary judgment 
            {
                res[xx][yy][zz]=res[w.x][w.y][w.z]+1;// Point distance after offset S Distance of 
                if(mp[xx][yy][zz]=='E')// eureka E spot , end 
                {
                    return res[xx][yy][zz];// Return steps 
                }
                q.push({xx,yy,zz});// The offset point joins the team , Continue to search 
            }
        }
        
    }
    return 0;// Can't find E, unsolvable 
}
int main()
{
    while(cin>>l>>r>>c&&l)
    {
        memset(res,-1,sizeof res);// Each time you enter a sample, you need to reset the map and steps 
        memset(mp,0,sizeof mp);
        for(int i=1;i<=l;i++)
        {
            for(int j=1;j<=r;j++)
            {
                for(int p=1;p<=c;p++)
                {
                    cin>>mp[i][j][p];
                    if(mp[i][j][p]=='S')xs=i,ys=j,zs=p;// Record S The location of 
                }
            }
        }
        int cnt=bfs();
        if(cnt!=0)printf("Escaped in %d minute(s).\n",cnt);
        else cout<<"Trapped!"<<endl;
    }
    return 0;
}