题意:三维空间求最短路,可前后左右上下移动。
分析:开三维数组即可。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 30 + 10;
char pic[MAXN][MAXN][MAXN];
bool vis[MAXN][MAXN][MAXN];
int sx, sy, sz;
int dr[] = {0, 0, 1, -1, 0, 0};
int dc[] = {1, -1, 0, 0, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};
int L, R, C;
bool judge(int x, int y, int z){
return x >= 0 && x < R && y >= 0 && y < C && z >= 0 && z < L;
}
int bfs(){
queue<int> x, y, z, step;
x.push(sx), y.push(sy), z.push(sz), step.push(0);
vis[sz][sx][sy] = true;
while(!x.empty()){
int tmpx = x.front(); x.pop();
int tmpy = y.front(); y.pop();
int tmpz = z.front(); z.pop();
int tmpstep = step.front(); step.pop();
for(int i = 0; i < 6; ++i){
int tx = tmpx + dr[i];
int ty = tmpy + dc[i];
int tz = tmpz + dz[i];
if(judge(tx, ty, tz)){
if(pic[tz][tx][ty] == 'E') return tmpstep + 1;
if(pic[tz][tx][ty] != '#' && !vis[tz][tx][ty]){
vis[tz][tx][ty] = true;
x.push(tx);
y.push(ty);
z.push(tz);
step.push(tmpstep + 1);
}
}
}
}
return -1;
}
int main(){
while(scanf("%d%d%d", &L, &R, &C) == 3){
if(!L && !R && !C) return 0;
memset(vis, false, sizeof vis);
for(int i = 0; i < L; ++i){
for(int j = 0; j < R; ++j){
scanf("%s", pic[i][j]);
for(int k = 0; k < C; ++k){
if(pic[i][j][k] == 'S'){
sz = i, sx = j, sy = k;
}
}
}
}
int ans = bfs();
if(ans == -1) printf("Trapped!\n");
else printf("Escaped in %d minute(s).\n", ans);
}
return 0;
}