Astria's Blog

主题

265-2 ​

1096. 地牢大师(BFS+三维数组) ​

原题链接

你现在被困在一个三维地牢中，需要找到最快脱离的出路！

地牢由若干个单位立方体组成，其中部分是不含岩石障碍的空单元格，可以直接通过；部分包含岩石障碍，无法通过。

向北、向南、向东、向西、向上或向下移动一个单元均需要一分钟。

你不能沿对角线移动，地牢边界都是坚硬的岩石，你不能走出边界范围。

请问，你有可能逃脱吗？如果可以，需要多长时间？

输入格式
输入包含多组测试数据。

每组数据第一行包含三个整数 L, R, C，分别表示地牢的层数，以及每一层的行数和列数。

接下来是 L 个矩阵，每个矩阵有 R 行 C 列，用来表示每一层地牢的具体状况。

每个字符描述一个地牢单元的状态：“#”表示岩石障碍，“.”表示空单元格，“S”表示你的起始位置，“E”表示终点。

每一个字符矩阵后面都会有一个空行。

当输入一行为“0 0 0”时，表示输入终止。

输出格式
每组数据输出一个结果，每个结果占一行。

如果能够逃脱地牢，则输出“Escaped in x minute(s).”，其中 x 为逃脱所需的最短时间。

如果不能逃脱地牢，则输出“Trapped!”。

数据范围
1 ≤ L, R, C ≤ 100

输入样例：

cpp
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

输出样例：

cpp
Escaped in 11 minute(s).
Trapped!

分析

  • 该地牢是立体的，故需要使用三维数组构建模型。
  • 要求第一次搜索到的路径即为最短时间，因此考虑使用 BFS。
  • 记录“S”和“E”的位置，“S”是搜索的起点，“E”是搜索的终点。
  • 搜索过程中每个位置需要向六个方向扩展，需要定义偏移量数组。

偏移量应用相关内容

  • 扩展的点需要满足：不越界、未被访问过、不是障碍“#”。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int l, r, c;  // 地牢参数
int px, py, pz, ex, ey, ez;  // (px, py, pz) 为 S 的位置，(ex, ey, ez) 为 E 的位置

char mp[N][N][N];  // 记录地牢
int ans[N][N][N];  // 存储答案
bool vis[N][N][N];  // 记录该点是否被访问过

struct point {  // 点的坐标
    int x, y, z;
};

queue<point> st;  // 搜索队列

int dx[] = {1, -1, 0, 0, 0, 0}, dy[] = {0, 0, 1, -1, 0, 0}, dz[] = {0, 0, 0, 0, 1, -1};  // 偏移量数组

int bfs(){
    while(!st.empty()){  // 当队列不为空时，扩展搜索当前节点
        auto p = st.front();
        for(int i = 0; i < 6; i++){
            int m_x = p.x + dx[i], m_y = p.y + dy[i], m_z = p.z + dz[i];  // 偏移之后的点的坐标
            if(m_x <= l && m_y <= r && m_z <= c && m_x >= 1 && m_y >= 1 && m_z >= 1 && !vis[m_x][m_y][m_z] && mp[m_x][m_y][m_z] != '#'){  // 判断条件
                vis[m_x][m_y][m_z] = 1;  // 更新该点走过的状态
                ans[m_x][m_y][m_z] = ans[p.x][p.y][p.z] + 1;  // 更新偏移后的点距离S的步骤
                if(mp[m_x][m_y][m_z] == 'E') return ans[m_x][m_y][m_z];  // 搜到E直接返回答案
                st.push({m_x, m_y, m_z});  // 将该点入队，继续扩展搜索
            }
        }
        st.pop();  // 队头扩展搜索完毕后出队
    }
    return 0;  // 所有的点扩展搜索完后若还未返回搜到E，说明无解
}

int main(){
    while(cin >> l >> r >> c && l && r && c){  // 多实例读入
        // 还原数据
        memset(ans, 0, sizeof(ans));
        memset(mp, 0, sizeof(mp));
        memset(vis, 0, sizeof(vis));
        while(!st.empty()){
            st.pop();
        }
        // 读入迷宫
        for(int i = 1; i <= l; i++){
            for(int j = 1; j <= r; j++){
                for(int k = 1; k <= c; k++){
                    cin >> mp[i][j][k];
                    if(mp[i][j][k] == 'S') px = i, py = j, pz = k;  // 记录起点S的坐标
                    if(mp[i][j][k] == 'E') ex = i, ey = j, ez = k;  // 记录终点E的坐标
                }
            }
        }

        vis[px][py][pz] = 1;  // 标记S已经走过
        st.push({px, py, pz}); // S点入队

        int cnt = bfs();  // 调用BFS搜索
        if(cnt != 0) printf("Escaped in %d minute(s).\n", cnt);
        else cout << "Trapped!" << endl;

        return 0;
    }
}