B - Dungeon Master (POJ - 2251)
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 30+5;
char b[N][N][N] = {{{0}}};
bool vis[N][N][N] = {{{0}}};
int l, r, c, ans = 0;
int dx[] = { 1, -1, 0, 0, 0, 0};
int dy[] = { 0, 0, 1, -1, 0, 0};
int dz[] = { 0, 0, 0, 0, 1, -1};
struct P {
int z, x, y;
int step;
};
P sp;
bool bfs() {
memset(vis, 0, sizeof(vis));
sp.step = 0;
queue<P> q;
q.push(sp);
vis[sp.z][sp.x][sp.y] = 1;
while(!q.empty()) {
P tp = q.front();
q.pop();
P np = tp;
for(int i=0; i<6; i++) {
int z = np.z = tp.z + dz[i];
int x = np.x = tp.x + dx[i];
int y = np.y = tp.y + dy[i];
np.step = tp.step+1;
if(z<0 || z>=l || x<0 || x>=r || y<0 || y>=c) {
continue;
}
if(b[z][x][y]=='#') {
continue;
}
if(b[z][x][y]=='E') {
ans = np.step;
return true;
}
if(b[z][x][y]=='.' && vis[z][x][y]==false) {
vis[z][x][y] = true;
q.push(np);
}
}
}
return false;
}
int main(void) {
while(scanf("%d%d%d", &l, &r, &c)==3 && l && r && c) {
ans = 0;
for(int i=0; i<l; i++) {
for(int j=0; j<r; j++) {
for(int k=0; k<c; k++) {
scanf(" %c", &b[i][j][k]);
if(b[i][j][k]=='S') {
sp.z = i;
sp.x = j;
sp.y = k;
}
}
}
}
if(bfs())
printf("Escaped in %d minute(s).\n", ans);
else
printf("Trapped!\n");
}
return 0;
}