固定 5×5 迷宫 BFS 求唯一最短路，入队时记录前驱并兼作访问标记，到终点后回溯再反转输出路径。
OJ: roj
题目 ID: 1255
难度:入门
标签:搜索BFS网格队列python
创建: 2026-09-30 02:01
更新: 2026-10-07 12:15
后置题目
roj 3080武士风度的牛B 直接复用 A 的「首次到达即最短距离、标记与判重合一份」这一 BFS 核心步骤，只是换成马的 8 位移并把前驱标记换成 dist 数组roj 3081乳草的入侵B 直接复用 A 教的网格 BFS 中首次入队即最短步数这一层数判定，只把四连通换成八连通并把单点到点距离改为全图最大层数roj 1360奇怪的电梯(lift)A 教的「BFS 首次入队即最短、入队时同时充当访问标记」正是 B 解法的那一步：B 把楼层当无权有向图顶点后，用 dist[A]=0 入队、dist 置 -1 兼作未访问标记、首次到达层号即最少按键次数，只是在同一 BFS 模板上换成动态出边与不可达输出 -1。roj 1330【例8.3】最少步数B 的正解把 A 教的「首次入队即最短步数、并用同一张表兼作访问标记」这套网格无权图 BFS 引擎与状态设计原样用在 100×100 棋盘上（代码里 dist 字典既存距离又判重），只是把源点从起点搬到终点 (1,1) 做一次反向预处理并叠加 12 种走法。roj 1253抓住那头牛B 的 main.cpp 直接复用 A 教的「无权图 BFS 按层扩展、首次入队即最短步数、dist=-1 兼作访问标记」这一步，只把网格四方向换成 -1/+1/*2 三种操作，并叠加 [0,2K] 搜索上界与 K<=N 时答案 N-K 的收口roj 1257Knight MovesA 教的「BFS 按层扩展、格子第一次入队即最短步数、入队即标记」正是 B 判定马步最少步数的核心一步，B 只把四方向邻接换成 8 个马步落点、单终点答案扩成多组样例，仍靠首次到达终点即返回该层步数。roj 1252走迷宫M4 反转修正：原登记为 roj/1252->roj/1255，但原 reason 自述的学习顺序与此相反。原 reason 自述「同模型的最简版本…本题在其上增加路径还原」，即 roj/1255（迷宫问题, r0）是基、roj/1252（走迷宫, r1）是加强。箭头确实写反，反转后 Δ=1 合规。roj 1248Dungeon MasterB 原样复用 A 教的「BFS 首次入队即最短步数、入队兼作访问标记」这一层号求最短路步骤，只把四方向二维网格换成六方向三维网格，无新增算法步骤，属模板级复用。roj 1191流感传染B 在多源 BFS 中复用 A 教的「入队时即登记访问标记、每格至多入队一次」这一步来标记已染病格，只是把单起点换成多个 @ 起点并叠加上按天分层的定长出队批次。shumeng CSP201409D最优配餐B 复用 A 教的「BFS 首次到达即最短步数」这一关键观察，只是把单源起点换成所有分店同时入队，再按需求量线性加权shumeng CSP201503D网络延时B 的 bfs() 直接复用 A 教的「无权图 BFS 按层扩展、首次入队即最短步数、dist=-1 兼作访问标记」这一步来量出到各点距离，两次 BFS 正是靠它找最远节点 u 再量出树直径，只是在此外层叠加了把电脑当叶子的建树与直径观察；A 特有的前驱回溯未被使用，故为模板级复用。shumeng CSP201604D游戏A 教的「无权网格 BFS 第一次入队即最短步数」正是 B 第二段所依赖的同一结论：B 只在第一阶段叠加时间维动态危险判定，第二阶段网格静态后仍按首次到达即最短的规则从多源点扩展求剩余步数，并额外补上多源点初值时刻与答案拼接。luogu P5908猫猫和企鹅B 的 main.cpp 沿用了 A 教的分层 BFS 状态设计：用 dist 数组（-1 兼作访问标记）按层 +1，靠「第一次入队即最短步数」把 BFS 层数当成到 1 号点的距离，只额外叠加限深（dist[u]==d 停止扩展）与根节点不计数的收口，并用一次遍历取代每只企鹅各自 DFS 的 O(n^2) 暴力。luogu P2960[USACO09OCT] Invasion of the Milkweed GB 的 main.py 直接复用 A 教的那一步「BFS 按层扩展、格子第一次入队即得最短步数」：把 distance 字典当分层距离表，靠 BFS 距离就是首次被占领时间，答案取最大距离，只是把四方向换成八邻域、起点行做 height-start_y 翻转，并额外叠加按最长距离取代到终点距离的收口。luogu P1332血色先锋队B 复用 A 教的无权网格 BFS 首次访问即最短距离这一观察，只是把单源改成所有感染源同时入队，得到每格最早感染时间luogu P1443马的遍历B 的正式解直接复用 A 教的网格无权图 BFS 按层扩展、以 -1 兼作访问标记、首次入队即最短步数这一步，只是把四方向换成马步 8 方向、单终点扩成全部格子
题目描述
给定一个 0（通路）或 1（墙壁）。每一步只能向上、下、左、右移动到相邻的通路格，不能斜走。求从左上角
思路
把每个通路格看成图中的一个顶点，四方向相邻的通路格之间连一条长度为
参考代码
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 02:01
# update_at: 2026-10-04 11:24
import sys
from collections import deque
N = 5 # 迷宫固定 5×5
def bfs_path(maze: list[list[int]]) -> list[tuple[int, int]]:
"""BFS 求左上到右下的最短路，返回从起点到终点的坐标序列（保证唯一解）。"""
# prev 记录每个格子从哪个格子走来，同时充当 vis：起点没有前驱，用 None 哨兵
prev: dict[tuple[int, int], tuple[int, int] | None] = {(0, 0): None}
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)): # 上下左右
inside = 0 <= nr < N and 0 <= nc < N and not maze[nr][nc]
if inside and (nr, nc) not in prev:
prev[(nr, nc)] = (r, c) # 首次到达即最短，登记前驱
queue.append((nr, nc))
path: list[tuple[int, int]] = [] # 从终点沿前驱回溯，再反转
cur: tuple[int, int] | None = (N - 1, N - 1)
while cur is not None:
path.append(cur)
cur = prev[cur]
return path[::-1]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
maze = [[next(data) for _ in range(N)] for _ in range(N)] # 逐行读入 5×5 迷宫，行内按列顺序消费
print('\n'.join(f'({r}, {c})' for r, c in bfs_path(maze)))
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-05 07:11
* update_at: 2026-10-05 07:11
*/
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 5; // 迷宫固定 5×5
const int DIR = 4; // 四个方向
int maze[N][N]; // 0 通路，1 墙壁
int pr[N][N], pc[N][N]; // 每个格子前驱坐标，同时充当访问标记：pr=-1 表示未访问
int dr[DIR] = {-1, 1, 0, 0};
int dc[DIR] = {0, 0, -1, 1};
// BFS 求最短路，同时记录前驱；首次到达某格即最短步数
void bfs_path() {
queue<pair<int, int> > q;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
pr[i][j] = -1;
pr[0][0] = -2; // 起点特殊标记，无前驱
pc[0][0] = -2;
q.push(make_pair(0, 0));
while (!q.empty()) {
int r = q.front().first;
int c = q.front().second;
q.pop();
for (int k = 0; k < DIR; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (maze[nr][nc] == 1) continue; // 墙
if (pr[nr][nc] != -1) continue; // 已访问
pr[nr][nc] = r; // 登记前驱
pc[nr][nc] = c;
q.push(make_pair(nr, nc));
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
cin >> maze[i][j];
bfs_path();
// 从终点沿前驱回溯到起点
int r = N - 1, c = N - 1;
pair<int, int> path[N * N];
int len = 0;
while (!(r == 0 && c == 0)) {
path[len++] = make_pair(r, c);
int nr = pr[r][c];
int nc = pc[r][c];
r = nr;
c = nc;
}
path[len++] = make_pair(0, 0);
// 反转输出
for (int i = len - 1; i >= 0; --i)
cout << '(' << path[i].first << ", " << path[i].second << ')' << '\n';
return 0;
}