• Published:

A three-dimensional dungeon can be represented as a grid of unit cubes. Some cubes are open, some are blocked by rock, and movement is allowed only one cube at a time: north, south, east, west, up, or down. Each move costs one minute. Diagonal moves are not allowed, and the outer boundary is solid rock, so there is no way out through the edges.

The question is whether escape is possible, and if so, how many minutes the shortest route takes.

Input begins with multiple test cases. For each case, the first line contains L, R, and C, the number of levels, rows per level, and columns per level. Then come L matrices of R rows and C columns. Each character describes one cell: # is rock, . is open space, S is the starting position, and E is the exit. A blank line follows each matrix. The input ends with a line containing 0 0 0.

For each case, print a single line. If escape is possible, print Escaped in x minute(s)., where x is the shortest time. Otherwise print Trapped!.

The limits are 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!

Because the maze is three-dimensional, a three-dimensional array is enough to store it. Since the problem asks for the first arrival at the exit, breadth-first search is the natural choice: in an unweighted grid, BFS reaches each cell in increasing distance order, so the first time it reaches E is the shortest path.

The implementation records the coordinates of S and E, starts BFS from S, and uses six direction offsets for the possible moves. A neighboring cell can be added to the queue only when it is inside the bounds, has not been visited, and is not a # cell. Distance values are stored in another 3D array, or can be carried along with the queue state.

Code:

#include <bits/stdc++.h>
using namespace std;

const int N=110;

int l,r,c;  // maze parameters
int px,py,pz,ex,ey,ez;  // p* is the position of S, e* is the position of E

char mp[N][N][N];  // stores the maze
int ans[N][N][N];  // stores the answer
bool vis[N][N][N];  // records whether the point has been visited

struct point{  // coordinates of a point
    int x,y,z;
};

queue<point> st;  // search queue

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

int bfs(){
    while(!st.empty()){  // while the front of the queue is not empty, expand it
        auto p=st.front();
        for(int i=0;i<6;i++){
            int m_x=p.x+dx[i],m_y=p.y+dy[i],m_z=p.z+dz[i];  // coordinates after offset
            if(m_x<=l&&m_y<=r&&m_z<=c&&m_x>=1&&m_y>=1&&m_z>=1&&!vis[m_x][m_y][m_z]&&mp[m_x][m_y][m_z]!='#'){  // check conditions
                vis[m_x][m_y][m_z]=1;  // update the visited state of this point
                ans[m_x][m_y][m_z]=ans[p.x][p.y][p.z]+1;  // update the distance from S to the offset point
                if(mp[m_x][m_y][m_z]=='E') return  ans[m_x][m_y][m_z];  // return the answer immediately upon finding E
                st.push({m_x,m_y,m_z});  // enqueue the point to continue expanding the search
            }
        }
        st.pop();  // dequeue after the front has been expanded
    }
    return 0;  // if no E was found after all points are expanded, there is no solution
}

int main(){
    while(cin>>l>>r>>c&&l&&r&&c){  // multiple test cases
        // reset data
        memset(ans,0,sizeof(ans));
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        while(st.size()){
            st.pop();
        }
        // read the maze
        for(int i=1;i<=l;i++){
            for(int j=1;j<=r;j++){
                for(int k=1;k<=c;k++){
                    cin>>mp[i][j][k];
                    if(mp[i][j][k]=='S') px=i,py=j,pz=k;  //
                    if(mp[i][j][k]=='E') ex=i,ey=j,ez=k;  //
                }
            }
        }

        vis[px][py][pz]=1;  // mark S as visited

        st.push({px,py,pz}); // enqueue point S

        int cnt=bfs();  // call search, starting from S

        if(cnt!=0) printf("Escaped in %d minute(s).\n",cnt);
        else cout<<"Trapped!"<<endl;
    }

    return 0;
}

Related Posts