【题解】地牢大师

题目链接：地牢大师

三维bfs

1. 通常这种棋盘类的题目都是二维，虽然变为三维其实做法也一样。队列，标记数组，距离数组三大件先准备好（距离数组可以与标记数组合并，但我比较喜欢分开），然后修改一下偏移量数组即可。
2. 改为三维后，在原来前后左右四个方向的基础上增加了上下两个方向，当在平面上移动时，第一维偏移量为 0 ；当在同一层移动时，第二、三维的偏移量为 0 。

bfs c++ 1619ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1e2 + 10;

int L, R, C;
string g[N][N];
int d[N][N][N];
bool st[N][N][N];
int dx[] = {0, 1, -1}, dy[] = {0, 1, 0, -1, 0}, dz[] = {0, 0, -1, 0, 1};

int bfs(int sx, int sy, int sz)
{
    memset(st, false, sizeof st);
    queue<pair<PII, int>> q;
    q.push({{sx, sy}, sz});
    d[sx][sy][sz] = 0;
    st[sx][sy][sz] = true;

    while (q.size())
    {
        int x = q.front().x.x, y = q.front().x.y, z = q.front().y;
        q.pop();

        for (int i = 0; i < 3; i ++ )
        {
            for (int j = 0; j < 5; j ++ )
            {
                if (i == 0 && j == 0) j ++ ;
                if (i && j) continue;
                int a = x + dx[i], b = y + dy[j], c = z + dz[j];
                if (a < 0 || a >= L || b < 0 || b >= R || c < 0 || c >= C) continue;
                if (st[a][b][c] || g[a][b][c] == '#') continue;
                if (g[a][b][c] == 'E') return d[x][y][z] + 1;
                d[a][b][c] = d[x][y][z] + 1;
                st[a][b][c] = true;
                q.push({{a, b}, c});
            }
        }
    }
    return -1;
}

int main()
{
    while (cin >> L >> R >> C, L && R && C)
    {
        for (int i = 0; i < L; i ++ )
            for (int j = 0; j < R; j ++ ) cin >> g[i][j];

        bool flag = false;
        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')
                    {
                        int t = bfs(i, j, k);
                        t == -1 ? printf("Trapped!\n") : printf("Escaped in %d minute(s).\n", t);
                        flag = true;
                        break; 
                    }
                }
                if (flag) break;
            }
            if (flag) break;
        }
    }
    return 0;
}