T07206: 我是最快的马
bfs, http://cs101.openjudge.cn/pctbook/T07206/
我们都知道，在中国象棋中，马是走日字步的。现给定马的起始坐标与终点坐标，求出马最快能到达的路线。如果有多条路线都是步数最少的，则输出路线的数目 注意，此时棋盘上可能会有一些其它的棋子，这些棋子是会憋马脚的，注意！
输入
前两行为起点坐标与终点坐标，第三行为一个数字M，之后的M行为棋盘上其它棋子的坐标(M<32,坐标行列值<=10)
输出
如果最快路线唯一，则输出路线。否则只输出一个数字，为最快路线的数目N
样例输入
0 0
2 4
1
1 1样例输出
(0,0)-(1,2)-(2,4)
《图 + BFS + 回溯（Path Reconstruction）》标准算法讲义版—— 这是高校算法课/竞赛教程里常用的规范写法，包括：
- 问题建模
- 图表示
- BFS 求最短路
- 记录最短路径条数
- 回溯恢复唯一路径
既可以作为教材，也可以直接讲给学生，非常清晰、标准化。
📘 算法讲义：图 + BFS + 回溯构造最短路径
- 问题模型（Graph Model）
象棋马所在的棋盘是一个 11×11 的网格图，每个格子对应图中的一个「节点」。
马的移动遵循象棋规则，包含 蹩马脚，因此每个节点到周围节点的边是否存在要按规则动态判断：
- 若马脚位置被障碍占据，则该方向无法移动；
- 若落点是障碍，也无法移动；
- 每次移动的代价均为 1（无权图）。
因此，该问题是一个 无权图最短路径 + 路径数量统计 + 唯一路径恢复 的综合问题。
2. 图的邻接规则（Implicit Graph）
我们不需要提前建好所有边，而是 BFS 时动态判断可移动方向。
每个方向包含两个坐标：
(dx, dy): 马的最终落点(bx, by): 马腿位置，用于判断蹩马脚
3. BFS：求最短路 + 最短路径条数
对无权图，最短路可以用 BFS 求。
我们维护三个结构：
3.1 dist[x][y]
记录起点到每个点的 最短步数 默认值为 INF。
3.2 ways[x][y]
记录到达 (x, y) 的 最短路径条数。
当访问一个新节点：
- 第一次到达：
dist[nx][ny] = dist[x][y] + 1ways[nx][ny] = ways[x][y] - 若再次遇到另一条同样长度的路径：
ways[nx][ny] += ways[x][y]
3.3 prev[x][y]
只在 唯一路径 的情况下记录路径的前驱。
- 初次访问且
ways[cur]==1→ 可以记前驱 - 若一个节点出现多条最短路径 → 立即将
prev[x][y] = None（说明不再唯一）
这是一个非常经典的技巧：
BFS 负责“是否唯一”判断； 若唯一才记录前驱，否则取消前驱。
这样既高效又不丢信息。
4. 回溯恢复唯一路径（Path Reconstruction）
若终点 (ex, ey) 满足：
ways[ex][ey] == 1说明最短路径唯一，可以从 prev[][] 中沿着前驱链逆向回溯：
end → ... → start然后反转即可得到：
start → ... → end若 ways > 1，题目要求只输出条数，不恢复路径。
⭐ 完整“讲义版”代码（结构最规范、最适合教学）
def solve():
from collections import deque
# ---------- 输入 ----------
sx, sy = map(int, input().split())
ex, ey = map(int, input().split())
M = int(input())
N = 11
obs = set()
for _ in range(M):
r, c = map(int, input().split())
obs.add((r, c))
# ---------- 马的图邻接规则：8 个方向 + 蹩马腿 ----------
moves = [
(2,1,1,0), (2,-1,1,0),
(-2,1,-1,0), (-2,-1,-1,0),
(1,2,0,1), (-1,2,0,1),
(1,-2,0,-1), (-1,-2,0,-1)
]
# ---------- BFS 核心 ----------
start = (sx,sy)
end = (ex,ey)
dist = {start: 0} # 最短距离
ways = {start: 1} # 最短路径数量
prev = {start: None} # 唯一路径的前驱
q = deque([start])
while q:
x, y = q.popleft()
d = dist[(x, y)]
for dx, dy, bx, by in moves:
# 1. 判断蹩马腿是否被障碍阻挡
legx, legy = x + bx, y + by
if 0 <= legx < N and 0 <= legy < N and (legx, legy) in obs:
continue
# 2. 判断落点合法
nx, ny = x + dx, y + dy
if not (0 <= nx < N and 0 <= ny < N):
continue
if (nx, ny) in obs:
continue
new_pos = (nx, ny)
nd = d + 1
# 3. 第一次到达该节点：更新最短路、路径数量、前驱
if new_pos not in dist:
dist[new_pos] = nd
ways[new_pos] = ways[(x, y)]
# 若前驱唯一路径才记录，之后若出现多路径会被取消
prev[new_pos] = (x, y) if ways[(x, y)] == 1 else None
q.append(new_pos)
# 4. 发现另一条同长度的路径：累加路径数量
elif nd == dist[new_pos]:
ways[new_pos] += ways[(x, y)]
prev[new_pos] = None # 不再唯一
# ---------- 输出 ----------
# 不可达
if end not in dist:
print("无解")
return
# 多条路径：只输出数目
if ways[end] > 1:
print(ways[end])
return
# 唯一路径：回溯重建路径
path = []
cur = end
while cur is not None:
path.append(cur)
cur = prev[cur]
path.reverse()
print("-".join(f"({x},{y})" for x, y in path))
solve()📍 教学重点总结
1. 本题是典型的图最短路径问题：无权图 → BFS 最短路
2. 额外统计「最短路径数量」：ways 数组
3. 只有在路径唯一时才记录 prev 才能回溯
4. 回溯构造路径：从终点沿 prev 一直追到起点
def solve():
import sys
from collections import deque
start_r, start_c = map(int, input().split())
end_r, end_c = map(int, input().split())
M = int(input())
obstacles = set()
for _ in range(M):
r, c = map(int, input().split())
obstacles.add((r, c))
# 棋盘坐标范围
MIN, MAX = 0, 10
# 马的走法：每个元组为(dx, dy, (block_dx, block_dy))
moves = [
(2, 1, (1, 0)), (2, -1, (1, 0)),
(-2, 1, (-1, 0)), (-2, -1, (-1, 0)),
(1, 2, (0, 1)), (-1, 2, (0, 1)),
(1, -2, (0, -1)), (-1, -2, (0, -1))
]
def in_bounds(pos):
r, c = pos
return MIN <= r <= MAX and MIN <= c <= MAX
start = (start_r, start_c)
end = (end_r, end_c)
# BFS：dist记录最短步数，ways记录最短路径数，prev在唯一路径时记录前驱便于重构路径
dist, ways, prev = {}, {}, {}
dist[start] = 0
ways[start] = 1
prev[start] = None
q = deque([start])
while q:
cur = q.popleft()
r, c = cur
for dx, dy, (br, bc) in moves:
# 计算“蹩马腿”所在位置
block = (r + br, c + bc)
# 如果该位置在棋盘上且被其它棋子占据，则该方向走法被阻挡
if in_bounds(block) and block in obstacles:
continue
newPos = (r + dx, c + dy)
if not in_bounds(newPos) or newPos in obstacles:
continue
nd = dist[cur] + 1
if newPos not in dist:
dist[newPos] = nd
ways[newPos] = ways[cur]
# 若当前点只有一条路径，则记录前驱；如果不唯一，则设为None
prev[newPos] = cur if ways[cur] == 1 else None
q.append(newPos)
elif nd == dist[newPos]:
ways[newPos] += ways[cur]
# 前驱不再唯一
prev[newPos] = None
# 如果目标不可达，输出"无解"
if end not in dist:
print("无解")
return
# 如果只有唯一一条最短路径，则重构路径输出格式 "(r,c)-(r,c)-..."
if ways[end] == 1:
path = []
cur = end
while cur is not None:
path.append(cur)
cur = prev[cur]
path.reverse()
route_str = "-".join("({},{})".format(r, c) for r, c in path)
print(route_str)
else:
# 多条最短路径则输出路径数目
print(str(ways[end]))
if __name__ == '__main__':
solve()
"""
0 0
2 2
0
16
"""另外，题面“坐标行列值<=10” 没有说明是否可以到-10。如果 MIN, MAX = -10, 10范围，上例输入情况下结果是54。