三维网格建成无权图，可通行格是顶点、六方向相邻连边，BFS 入队即标记，命中 E 的层号就是最短分钟数。
OJ: roj
题目 ID: 1248
难度:普及-
标签:图论最短路搜索BFS网格python
创建: 2026-09-30 01:34
更新: 2026-10-07 12:15
前置题目
roj 1255迷宫问题B 原样复用 A 教的「BFS 首次入队即最短步数、入队兼作访问标记」这一层号求最短路步骤，只把四方向二维网格换成六方向三维网格，无新增算法步骤，属模板级复用。roj 1335【例2-4】连通块B 的三维网格 BFS 在六方向扩展时沿用 A 明确点出的「入栈/入队即标记」这一状态设计（先判界再判障碍、命中即就地标记 seen），只是把连接块计数换成 BFS 层号即最短分钟数并叠加三维偏移与多组数据解析，属模板级复用。roj 1329【例8.2】细胞B 的三维六方向 BFS 直接沿用 A 明确点名为「可迁移实现习惯」的入队即标记状态设计（B 代码在 push 前写 seen=true），保证每格只展开一次，只在其上叠加层号当最短分钟数、多组数据解析与三维坐标偏移扩展。
题目描述
你被困在一个 #（不可通过）、.（可通行）、S（起点，唯一）或 E（出口，唯一）。每次只能朝上下前后左右六个方向之一移动到相邻格，耗时 1 分钟；不可对角线移动。求 S 到 E 的最少分钟数，不可达输出 Trapped!。多组数据，每组先给 L R C，再依次给 0 0 0 结束。样例 1：3 4 5 + S..../.###./.##../###.# + ####/####/##.##/##... + ####/####/#.###/####E → Escaped in 11 minute(s).；样例 2：1 3 3 + S##/#E#/### → Trapped!。
思路
把三维网格建成无权图：可通行格是顶点，六方向相邻就连一条无向边，S 到 E 的最短距离就是答案。边权全为 1，所以从 S 出发 BFS 的层号就是"已用分钟数"，命中 E 的层号直接返回；入队即标记保证每格只展开一次，复杂度
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 01:36
# update_at: 2026-09-30 01:36
import sys
WALL = ord('#') # 网格里存的是字节值，'#' 的字节值是 35，不可通行单元的判据
START, EXIT = ord('S'), ord('E')
# 六个方向的 (层, 行, 列) 偏移：层 ±1 是上下，行 ±1 是前后，列 ±1 是左右
DIRS: tuple[tuple[int, int, int], ...] = (
(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)
)
def find(dungeon: list[list[bytes]], key: int) -> tuple[int, int, int]:
"""定位标记字符 key（S 或 E）所在的 (层, 行, 列)；题面保证它出现且只出现一次。"""
return next(
(l, r, c)
for l, layer in enumerate(dungeon)
for r, row in enumerate(layer)
for c in range(len(row))
if row[c] == key
)
def escape_minutes(
dungeon: list[list[bytes]], start: tuple[int, int, int], target: tuple[int, int, int]
) -> int | None:
"""六方向 BFS 逐层扩展，返回 start→target 的最少分钟数；不可达返回 None。"""
L, R, C = len(dungeon), len(dungeon[0]), len(dungeon[0][0])
seen = {start}
frontier = [start] # 恰好用 minutes 分钟能站到的所有格子
minutes = 0
while frontier:
nxt: list[tuple[int, int, int]] = [] # 再多走一分钟能站到的格子
for l, r, c in frontier:
if (l, r, c) == target:
return minutes
for dl, dr, dc in DIRS:
nl, nr, nc = l + dl, r + dr, c + dc
in_range = 0 <= nl < L and 0 <= nr < R and 0 <= nc < C # 先判界，避免越界读
can_step = in_range and dungeon[nl][nr][nc] != WALL and (nl, nr, nc) not in seen
if can_step:
seen.add((nl, nr, nc)) # 入队即标记，同一个格子不会重复扩展
nxt.append((nl, nr, nc))
frontier, minutes = nxt, minutes + 1
return None
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
out: list[str] = []
while True:
L, R, C = int(next(data)), int(next(data)), int(next(data))
if L == 0 and R == 0 and C == 0: # 三个 0 表示输入结束
break
# 每层 R 行、每行 C 个字符；层与层之间的空行被 read().split() 当作空白丢掉
dungeon = [[next(data) for _ in range(R)] for _ in range(L)]
minutes = escape_minutes(dungeon, find(dungeon, START), find(dungeon, EXIT))
out.append(f"Escaped in {minutes} minute(s)." if minutes is not None else "Trapped!")
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-04 21:00
* update_at: 2026-10-04 21:00
*/
// main.cpp：三维迷宫 BFS 求 S 到 E 的最少分钟数；六方向（层±1 / 行±1 / 列±1）扩展。
#include <iostream>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
const int MAXL = 35; // L、R、C 都不超过 30，留一点冗余
const int MAXR = 35;
const int MAXC = 35;
char dungeon[MAXL][MAXR][MAXC]; // 三维网格，存原字符 '#' '.' 'S' 'E'
// 六个方向的 (层, 行, 列) 偏移：层 ±1 是上下，行 ±1 是前后，列 ±1 是左右
int dl[6] = { 1, -1, 0, 0, 0, 0 };
int dr[6] = { 0, 0, 1, -1, 0, 0 };
int dc[6] = { 0, 0, 0, 0, 1, -1 };
bool seen[MAXL][MAXR][MAXC]; // BFS 入队即标记，保证每格只展开一次
struct Pos {
int l, r, c;
};
// 六方向 BFS：返回 start 到 target 的最少分钟数；不可达返回 -1
int bfs(int L, int R, int C, Pos start, Pos target) {
queue<Pos> q;
q.push(start);
seen[start.l][start.r][start.c] = true;
int minutes = 0;
while (!q.empty()) {
int sz = (int)q.size(); // 当前层（恰好 minutes 分钟可达）的格子数
for (int i = 0; i < sz; i++) {
Pos cur = q.front(); q.pop();
if (cur.l == target.l && cur.r == target.r && cur.c == target.c) {
return minutes;
}
for (int k = 0; k < 6; k++) {
int nl = cur.l + dl[k];
int nr = cur.r + dr[k];
int nc = cur.c + dc[k];
// 先判界，再判墙，再判未访问
if (nl < 0 || nl >= L || nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (dungeon[nl][nr][nc] == '#') continue;
if (seen[nl][nr][nc]) continue;
seen[nl][nr][nc] = true; // 入队即标记
q.push({nl, nr, nc});
}
}
minutes++;
}
return -1; // S 与 E 不连通
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int L, R, C;
while (cin >> L >> R >> C) {
if (L == 0 && R == 0 && C == 0) break;
Pos start{-1, -1, -1}, target{-1, -1, -1};
for (int l = 0; l < L; l++) {
for (int r = 0; r < R; r++) {
string row;
cin >> row;
for (int c = 0; c < C; c++) {
dungeon[l][r][c] = row[c];
if (row[c] == 'S') start = {l, r, c};
else if (row[c] == 'E') target = {l, r, c};
}
}
}
// 每组数据前清空 seen 数组实际用到的范围（L、R、C 都 ≤ 30）
for (int l = 0; l < L; l++)
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
seen[l][r][c] = false;
int ans = bfs(L, R, C, start, target);
if (ans >= 0) cout << "Escaped in " << ans << " minute(s)." << '\n';
else cout << "Trapped!" << '\n';
}
return 0;
}