uva : 532 - Dungeon Master

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include < cstdio > #include < queue > using namespace std; char dungeon[32][32][32]; int Distance[32][32][32]; int L, R, C; const int direction[6][3] = { { -1, 0, 0 }, { 1, 0, 0 }, { 0, -1, 0 }, { 0, 1, 0 }, { 0, 0, -1 }, { 0, 0, 1 } }; struct point_type { int x; int y; int z; }; int BFS(int i, int j, int k) { Distance[i][j][k] = 0; queue < point_type > q; q.push(point_type { i, j, k }); dungeon[i][j][k] = '#'; point_type cur, nxt; while (!q.empty()) { cur = q.front(); q.pop(); for (int i = 0; i < 6; ++i) { nxt.x = cur.x + direction[i][0]; nxt.y = cur.y + direction[i][1]; nxt.z = cur.z + direction[i][2]; if (nxt.x < 0 || nxt.x >= L || nxt.y < 0 || nxt.y >= R || nxt.z < 0 || nxt.z >= C) continue; if (dungeon[nxt.x][nxt.y][nxt.z] != '#') { Distance[nxt.x][nxt.y][nxt.z] = Distance[cur.x][cur.y][cur.z] + 1; if (dungeon[nxt.x][nxt.y][nxt.z] == 'E') return Distance[nxt.x][nxt.y][nxt.z]; dungeon[nxt.x][nxt.y][nxt.z] = '#'; q.push(nxt); } } } return -1; } int main() { while (scanf("%d%d%d", & L, & R, & C)) { if (!L && !R && !C) break; int start_i, start_j, start_k; for (int i = 0; i < L; ++i) { for (int j = 0; j < R; ++j) { scanf("%s", dungeon[i][j]); for (int k = 0; k < C; ++k) if (dungeon[i][j][k] == 'S') { start_i = i; start_j = j; start_k = k; } } } int minute = BFS(start_i, start_j, start_k); if (minute != -1) printf("Escaped in %d minute(s).\n", minute); else printf("Trapped!\n"); } return 0; }