2025年4月12日 星期六

UVa _ 00532 _ Dungeon Master

 #include <iostream>

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN = 32;

char dungeon[MAXN][MAXN][MAXN];

int Distance[MAXN][MAXN][MAXN];

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 start_i, int start_j, int start_k) {

    // keypoint: Init Distance (-1 = not visited)

    for (int i = 0; i < L; ++i)

        for (int j = 0; j < R; ++j)

            for (int k = 0; k < C; ++k)

                Distance[i][j][k] = -1;

    // keypoint: BFS queue

    queue<point_type> q;

    q.push({start_i, start_j, start_k});

    Distance[start_i][start_j][start_k] = 0;

    while (!q.empty()) {

        point_type cur = q.front();

        q.pop();

        // keypoint: Found end

        if (dungeon[cur.x][cur.y][cur.z] == 'E')

            return Distance[cur.x][cur.y][cur.z];

        for (int i = 0; i < 6; ++i) {

            point_type nxt = {cur.x + direction[i][0], cur.y + direction[i][1], cur.z + direction[i][2]};

            // keypoint: Boundary check

            if (nxt.x < 0 || nxt.x >= L || nxt.y < 0 || nxt.y >= R || nxt.z < 0 || nxt.z >= C) continue;

            // keypoint: Wall check

            if (dungeon[nxt.x][nxt.y][nxt.z] == '#') continue;

            // keypoint: Visited check

            if (Distance[nxt.x][nxt.y][nxt.z] != -1) continue;

            Distance[nxt.x][nxt.y][nxt.z] = Distance[cur.x][cur.y][cur.z] + 1;

            q.push(nxt);

        }

    }

    return -1; // keypoint: No path

}

int main() {

    while (scanf("%d%d%d", &L, &R, &C) == 3) {

        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;

}