AcWing_1096 地牢大师(三维bfs、模板)

#include <bits/stdc++.h>
using namespace std;
int l, r, c;
const int N = 110;
char m[N][N][N];
struct point{
    int x, y, z;
    bool operator == (const point &t) const{
        return x == t.x && y == t.y && z == t.z;
    }
};
point st, ed;
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
int dist[N][N][N];
int bfs(){
    memset(dist, -1, sizeof dist);
    queue<point> q;
    q.push(st);
    dist[st.z][st.x][st.y] = 0;
    if(st == ed) return 0;
    while(!q.empty()){
        point t = q.front();
        q.pop();
        for(int i = 0; i <= 5; i ++){
            point tt = {t.x + dx[i], t.y + dy[i], t.z + dz[i]};
            if(tt.x < 0 || tt.x >= r || tt.y < 0 || tt.y >= c || tt.z < 0 || tt.z >= l) continue;
            if(m[tt.z][tt.x][tt.y] == '#') continue;
            if(dist[tt.z][tt.x][tt.y] != -1) continue;
            dist[tt.z][tt.x][tt.y] = dist[t.z][t.x][t.y] + 1;
            if(tt == ed) return dist[tt.z][tt.x][tt.y];
            q.push(tt);
        }
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(1){
        cin >> l >> r >> c;
        if(!l && !r && !c) break;
        for(int i = 0; i <= l - 1; i ++) for(int j = 0; j <= r - 1; j ++) cin >> m[i][j];
        for(int i = 0; i <= l - 1; i ++) for(int j = 0; j <= r - 1; j ++) for(int k = 0; k <= c - 1; k ++){
            if(m[i][j][k] == 'S') st = {j, k, i};
            if(m[i][j][k] == 'E') ed = {j, k, i};
        }
        int res = bfs();
        if(res == -1) cout << "Trapped!\n";
        else cout << "Escaped in " << res << " minute(s).\n";
    }
    return 0;
}