原题链接：http://poj.org/problem?id=2251
在三维空间内做BFS。
View Code
#include <stdio.h> #include <string.h> #include <queue> using namespace std; int L, R, C, ans, sx, sy, sz, ex, ey, ez; char maze[101][101][101]; bool vis[101][101][101]; int dr[6][3] = {{0, 0, 1}, {0, 0, -1}, {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}}; struct loc { int x, y, z, step; }; bool bfs() { loc s, tmp; s.x = sx, s.y = sy, s.z = sz, s.step = 0; vis[sx][sy][sz] = true; queue<loc> q; q.push(s); while(!q.empty()) { loc cur = q.front(); q.pop(); int cx = cur.x; int cy = cur.y; int cz = cur.z; int cstep = cur.step; for(int i = 0; i < 6; i ++) { int x = cx + dr[i][0]; int y = cy + dr[i][1]; int z = cz + dr[i][2]; if(x < 1 || x > C || y < 1 || y > R || z < 1 || z > L) continue; if(maze[x][y][z] == '.' && !vis[x][y][z]) { vis[x][y][z] = true; tmp.x = x, tmp.y = y, tmp.z = z, tmp.step = cstep + 1; q.push(tmp); } if(maze[x][y][z] == 'E') { ans = cstep + 1; return true; } } } return false; } int main() { int i, j, k; while(scanf("%d%d%d", &L, &R, &C), (L || R ||C)) { for(i = 1; i <= L; i ++) { for(j = 1; j <= R; j ++) { getchar(); for(k = 1; k <= C; k ++) { scanf("%c", &maze[k][j][i]); if(maze[k][j][i] == 'S') sz = i, sy = j, sx = k; if(maze[k][j][i] == 'E') ez = i, ey = j, ex = k; } } getchar(); } memset(vis, false, sizeof(vis)); if(bfs()) printf("Escaped in %d minute(s).\n", ans); else printf("Trapped!\n"); } return 0; }