AcWing 1096. 地牢大师

简单题，BFS + 三维数组，套路跟二维数组相同，注意每次需要清空队列！可以在bfs()内创建队列。

另外对于三元数据的存储，我这里使用的是嵌套pairpair<int, pair<int, int>>存储的，更建议使用struct结构体存储。

参考代码1（嵌套pair）

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;
typedef long long ll;
typedef pair<int, pair<int, int>> PIII;

const int N = 110;

int l, r, c;
char g[N][N][N];
int dist[N][N][N];
int dx[6] = { -1, 0, 1, 0, 0, 0 }, dy[6] = { 0, 1, 0, -1, 0, 0 }, dz[6] = { 0, 0, 0, 0, 1, -1 };

void bfs(int x, int y, int z)
{
    queue<PIII> q;
    dist[z][x][y] = 0;
    q.push({ z, {x, y } });

    while (!q.empty()) {
        auto t = q.front(); q.pop();
        int tz = t.first, tx = t.second.first, ty = t.second.second;
        for (int i = 0; i < 6; i++) {
            int z = tz + dz[i], x = tx + dx[i], y = ty + dy[i];
            if (z >= 0 && z < l && x >= 0 && x < r && y >= 0 && y < c && dist[z][x][y] == -1 && g[z][x][y] != '#') {
                dist[z][x][y] = dist[tz][tx][ty] + 1;
                q.push({ z, {x, y} });
                if (g[z][x][y] == 'E') return;
            }
        }
    }
}

int main()
{
    while (1) {
        memset(dist, -1, sizeof dist);
        scanf("%d%d%d", &l, &r, &c);
        if (!l && !r && !c) break;

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                scanf("%s", g[i][j]);
            }
            char hang[110];
            scanf("%c", hang);
        }

        // 找出起点和终点
        int sx = 0, sy = 0, sz = 0, ex = 0, ey = 0, ez = 0;
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                for (int k = 0; k < c; k++) {
                    if (g[i][j][k] == 'S') sz = i, sx = j, sy = k;
                    if (g[i][j][k] == 'E') ez = i, ex = j, ey = k;
                }
            }
        }

        bfs(sx, sy, sz);

        if (dist[ez][ex][ey] == -1) printf("Trapped!\n");
        else printf("Escaped in %d minute(s).\n", dist[ez][ex][ey]);
    }

    return 0;
}

参考代码2（struct）

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;

// 定义三维坐标结构体
struct Pos {
    int z, x, y;  // 层、行、列
};

int l, r, c;
char g[N][N][N];
int dist[N][N][N];
int dx[6] = { -1, 0, 1, 0, 0, 0 }, dy[6] = { 0, 1, 0, -1, 0, 0 }, dz[6] = { 0, 0, 0, 0, 1, -1 };

void bfs(int start_x, int start_y, int start_z) {
    queue<Pos> q;
    dist[start_z][start_x][start_y] = 0;
    q.push({ start_z, start_x, start_y });  // 使用emplace直接构造

    while (!q.empty()) {
        auto t = q.front(); q.pop();

        // 直接访问结构体成员
        for (int i = 0; i < 6; i++) {
            int z = t.z + dz[i], x = t.x + dx[i], y = t.y + dy[i];

            if (z >= 0 && z < l && x >= 0 && x < r && y >= 0 && y < c
                && dist[z][x][y] == -1 && g[z][x][y] != '#') {

                dist[z][x][y] = dist[t.z][t.x][t.y] + 1;
                q.push({ z, x, y });  // 压入新坐标

                if (g[z][x][y] == 'E') return;
            }
        }
    }
}

int main() {
    while (true) {
        memset(dist, -1, sizeof dist);
        scanf("%d%d%d", &l, &r, &c);
        if (!l && !r && !c) break;

        // 读取输入
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                scanf("%s", g[i][j]);
            }
            getchar();  // 读取换行符
        }

        // 查找起点终点
        Pos start = { 0, 0, 0 }, end = { 0, 0, 0 };
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                for (int k = 0; k < c; k++) {
                    if (g[i][j][k] == 'S') start = { i, j, k };
                    if (g[i][j][k] == 'E') end = { i, j, k };
                }
            }
        }

        bfs(start.x, start.y, start.z);

        if (dist[end.z][end.x][end.y] == -1) {
            printf("Trapped!\n");
        }
        else {
            printf("Escaped in %d minute(s).\n", dist[end.z][end.x][end.y]);
        }
    }
    return 0;
}