01 / 本课学习路线
本课学习路线
阅读与推演约 116 分钟，练习约 65 分钟，进阶练习另需约 50 分钟
02 / 学习目标与先修自测
学完本课你能做什么，以及开始前需要会什么
本课只有一套代码：源点入队 → 整层出队 → 四方向过滤后入队并标记 → 走完一层计数。四道题换的只是「第 0 层是谁」「哪些邻居能入队」「答案怎么从层数得到」。
| 学完后能做的事 | 正文位置 | 检查方式 |
|---|---|---|
| 解释多源 BFS 为什么把所有源点当第 0 层，通过（AC）P3702 | 第 04、08 节 | 自查第 2 条、必做任务 1 |
| 说出访问标记为什么必须在入队时打 | 第 03 节、第 09 节错误表 | 自查第 3 条 |
| 不看资料写出「每轮先取队列长度再整层处理」的层数统计写法 | 第 04 节模板 | 自查第 4 条、练习 4 |
| 说出 -1（无法全覆盖）的判定依据是剩余待改造格数，而不是队列空 | 第 04 节 | 自查第 5 条 |
| 给单源 BFS 加移动约束并在结束后选答案，通过 P3708 | 第 05、08 节 | 必做任务 2 |
先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你已完成「二维数组、坐标与边界处理」与上一课。
| 题号 | 题目 | 补看位置 |
|---|---|---|
| 自测 1 | 写出上下左右四个方向的 (dr, dc)，并说出 (r + dr, c + dc) 在 rows×cols 网格里的越界判断。 | 二维数组、坐标与边界处理 |
| 自测 2 | q = deque([(0, 0)])，入队 (1, 2) 和出队各写一句；len(q) 在循环里为什么要先取出来？ | 上一课第 03 节与模块与 import |
| 自测 3 | 建一个 3 行 4 列、全为 False 的二维列表；[[False] * 4] * 3 为什么不行？ | 列表 |
| 自测 4 | 一行 m×n 个整数，怎样折成 m 行 n 列的网格？ | 列表切片 |
| 自测 5 | 不知道行数、每行若干个 YES/NO/NA，怎样读到文件尾并按空格拆？ | 标准输入输出与首次独立提交 |
展开先修自测答案
自测 1：((1, 0), (−1, 0), (0, 1), (0, −1))；越界判断 0 <= nr < rows and 0 <= nc < cols，先判越界再读网格。
自测 2：q.append((1, 2))、r, c = q.popleft()。整层处理时队列一边出一边进，for _ in range(len(q)) 在循环开始时把长度定死，才能只处理当前这一层。
自测 3：[[False] * 4 for _ in range(3)]。[[False] * 4] * 3 三行是同一个列表对象，改一格三行一起变。
自测 4：grid = [vals[i * n:(i + 1) * n] for i in range(m)]。P3700 的输入就是这种一行铺开的形式。
自测 5：[line.split() for line in sys.stdin.read().split("\n") if line.strip()]——跳过空行；P3702 的输入没有给行数。
03 / 概念与术语
层、源点、访问标记、多源、过滤条件
BFS 的正确性来自一句话：队列里的格子按「离源点的步数」从小到大排队，所以第一次到达某格时走的就是最短步数（每步代价相同时）。
| 术语 | 含义 | 代码写法 |
|---|---|---|
| 源点 | BFS 的起点集合，第 0 层 | 开始前全部 q.append((r, c)) |
| 层 | 离源点恰好 d 步的全部格子 | for _ in range(len(q)) 处理一整层 |
| 访问标记 | 记录哪些格子已经进过队列，避免重复 | seen[nr][nc] = True，或直接改网格值 |
| 入队即标记 | 在 append 的同一刻打标记，而不是出队时 | 同一格至多入队一次 |
| 多源 BFS | 第 0 层有多个源点，其余不变 | P3702 |
| 过滤条件 | 决定哪些邻居能入队：不越界、未访问、题目的约束 | P3708 加 abs(高度差) <= k |
| 层数即答案 | 天数 / 最短步数 / 衰减量都等于层数 | 走完一层 days += 1 |
| P3702 火星改造 | P3708 周末爬山 | P3700 计算网络信号 | P3706 跳马问题 | |
|---|---|---|---|---|
| 第 0 层 | 所有 YES 格 | 起点 (0,0) | 唯一信号源 | 每匹马各自跑一次 |
| 入队过滤 | 邻格是 NO | 邻格高度差 ≤ k | 邻格是空旷 0，且强度未衰减到 0 | 马步八方向、不超过步数上限 |
| 答案 | 待改造格归零的天数；否则 -1 | 可达格里最高、同高步数短 | 目标格的值 = 源强度 − 层数 | 每格所有马步数之和的最小值 |
P3708 的选择放在 BFS 之后做：先标出全部可达格与步数，再在可达集合里选最高、同高选步数短——不要在搜索途中边走边比。
标记打在入队那一刻
等到出队再标记，同一格可能被多个邻居各加入队列一次，重复的格子再各自扩散，队列规模和运行时间都会增加，在 500×500 这样的网格上可能超时；带计数的题（P3702 的待改造格数）还会被多减。入队即标记，保证每格最多入队一次。
补充学习（选学）BFS、DFS 与递归深度约 5 分钟什么时候必须用 BFS，什么时候深度优先搜索（DFS）也行，9 万层递归的风险
只问「连通到哪些格子」时 BFS、DFS 都行，答案与访问顺序无关；要「最短几步」「第几天」这类按层计数的答案时（无权或等权扩散），才必须用 BFS。边权不同的最短路要换成 Dijkstra 算法（模块 3 · 第 5 课）。
Python 默认递归上限约 1000 层：一张 300×300 全是可走格的地图，DFS 最坏递归 9 万层会直接抛出递归深度超限错误（RecursionError）。判题机上安全的写法：BFS 用队列，或把 DFS 递归换成显式栈——已访问标记（seen）、方向数组一字不改，只换容器。
04 / 多源扩散：P3702
所有源点同时入队，层数就是天数
P3702「火星改造」：若干行、每行若干个 YES / NO / NA（行数不在输入里）；YES 是宜居区（源点），NO 待改造，NA 死亡区不可穿过；每个太阳日所有宜居区同时向四方向扩散；输出全部 NO 变成 YES 的天数，无法全部改造输出 -1。
多源 BFS 逐天推演（3×3：源点 (0,0)、(2,2)，一个死亡区）
初始: Y N N 第 0 层队列: (0,0) (2,2) 待改造格数 = 6
X N N
N N Y
第 1 层: (0,1) (1,2) (2,1) 被改造 待改造格数 6→3
第 2 层: (0,2) (1,1) (2,0) 被改造 待改造格数 3→0
全部 N 改造完成 → 输出 2；若有 N 被 X 围住，BFS 正常结束但待改造格数 > 0 → 输出 -1| 天 | 本层出队 | 新改造的格子 | 剩余待改造 |
|---|---|---|---|
| 0 | — | —（源点 (0,0)、(0,1)、(2,2) 入队） | 5 |
| 1 | (0,0) (0,1) (2,2) | (1,0)、(0,2)、(1,1)、(1,2)、(2,1) | 0 |
五个 NO 都与某个 YES 相邻，一天全部改造完 → 输出 1。循环条件是「队列非空且待改造格数 > 0」：待改造格数归零后不再多算一天；没有 NO 时循环一次都不进，输出 0。
无法全覆盖：YES NA NO / NA NA NA / NO NO NO
源点 (0,0) 四周只有 NA 与边界 → 第 1 层无新格，队列空 待改造格数仍是 4 → 输出 -1（判定依据是待改造格数，不是「队列空了」）
多源广度优先搜索练习模板
Pythonfrom collections import deque
import sys
def bfs(grid):
rows, cols = len(grid), len(grid[0])
q = deque()
todo = 0
for r in range(rows):
for c in range(cols):
# 待完成 1：哪些格子作为第 0 层源点入队，哪些格子计入待改造格数 todo
...
days = 0
while q and todo:
for _ in range(len(q)): # 只处理当前这一层
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
# 待完成 2：越界、不可走、已访问三重过滤，并在入队时标记
...
days += 1 # 走完一层，时间过一天
# 待完成 3：仍有未改造格时按题目要求输出什么
...层数统计的标准写法：每轮先取 len(q)，把当前层整层处理完再让天数加一。每个格子至多入队一次，时间 O(rows×cols)——多源与单源同复杂度，源点多只是第 0 层更宽。补看：腐烂的橘子动画。
05 / 带约束的单源 BFS：P3708
约束只影响哪些邻居能入队；答案在 BFS 结束后再选
P3708「周末爬山」：第一行 m n k，之后 m 行 n 列高度（0 平地、1～9 山）；从 (0,0) 出发，每步只能走四邻且高度差 ≤ k；输出能到达的最高峰高度与到它的最短步数，同高取步数短；没有比起点更高的可达格时输出 0 0。
| 层（步数） | 本层到达的格子（高度） | 为什么 |
|---|---|---|
| 0 | (0,0)=0 | 起点 |
| 1 | (0,1)=1、(1,0)=1 | 与 0 差 1；(1,1)=5 与谁都差 ≥ 2，永远进不来 |
| 2 | (0,2)=2、(2,0)=2 | 与 1 差 1 |
| 3 | (1,2)=3、(2,1)=3 | 与 2 差 1 |
| 4 | (2,2)=4 | 与 3 差 1 |
可达格里最高是 4（(2,2)），步数 4 → 输出 4 4。(1,1)=5 更高但到不了。同高取步数短：同一高度先被到达的层数更小，按层遍历保证了这一点。
两个边界：起点就是最高 / 同高不同步数
1 3 2 / 5 3 1：起点高度 5，可达格没有比 5 更高的 → 按题目页参考题解输出 0 0 2 3 3 / 0 3 1 / 1 1 3：(0,1)=3 在第 1 层、(1,2)=3 在第 3 层 → 同高取步数短 → 3 1 2 2 1 / 0 0 / 0 0：全是平地，没有山峰 → 0 0
「第一次到达即最短步数」成立的前提是每一步代价相同——本题每步都是 1。数据范围 500×500 = 2.5×10⁵ 格，每格至多入队一次，BFS 远在时限内；DFS 递归在这种规模上会超过递归上限（第 03 节补充）。
06 / 衰减扩散：P3700
信号值 = 源强度 − 层数，衰减到 0 就停止扩散
P3700「计算网络信号」：第一行 m n，第二行 m×n 个整数铺开（0 空旷、正数信号源强度、-1 阻隔物，只有一个信号源），第三行目标 i j（从 0 起）；信号每向四邻走一格衰减 1，可以绕过阻隔物；输出目标格的信号值，未覆盖到输出 0。
| 行 | 地图（-1 阻隔，4 信号源） | 扩散后各格信号值 |
|---|---|---|
| 0 | 0 0 0 -1 0 | 0 0 1 -1 1 |
| 1 | 0 0 0 0 0 | 0 1 2 3 2 |
| 2 | 0 0 -1 4 0 | 0 0 -1 4 3 |
| 3 | 0 0 0 0 0 | 0 1 2 3 2 |
| 4 | 0 0 0 0 -1 | 0 0 1 2 -1 |
| 5 | 0 0 0 0 0 | 0 0 0 1 0 |
第 1 层（值 3）：(1,3)、(2,4)、(3,3)；第 2 层（值 2）：(1,2)、(1,4)、(3,2)、(3,4)、(4,3)；第 3 层（值 1）：(0,2)、(0,4)、(1,1)、(3,1)、(4,2)、(5,3)。注意 (0,4)：(0,3) 是阻隔物，只能走 (2,3)→(2,4)→(1,4)→(0,4) 三步，所以是 1 而不是 2。目标 (1,4) 在第 2 层 → 输出 2，与题面一致。(2,2) 是阻隔物，绕行由 BFS 自然完成；值 0 的格子不再入队。
同一格可能由不同路径到达，题面要求取较大值——BFS 按层扩散，第一次到达时层数最小、信号值最大，之后不再改写，天然满足。目标格若是信号源本身就输出源强度；被阻隔物围住或超出衰减范围则保持 0。
补充学习（选学）衰减扩散：用层数计算信号强度约 4 分钟P3700 的信号强度 = 源强度 − 层数
计算网络信号（P3700）本质仍是单源 BFS：信号每走一格衰减 1，所以某格的信号值 = 源强度 − 它所在的层数。衰减到 0 就不再入队——相当于给 BFS 加了「最多扩散 x 层」的截止条件。阻隔物是不可走格，绕行由 BFS 自然处理。
07 / 多次 BFS 再汇总：P3706
每匹马各自 BFS，逐格把步数加起来取最小
P3706「跳马问题」：第一行 m n，之后 m 行棋盘，数字 k 表示一匹最多走 k 步的马，. 表示空；马走「日」字（八方向）；求所有马能否走到同一格，能则输出最小总步数，否则 0。
| 格子 | (0,0) 马的步数 | (1,2) 马的步数 | 合计 |
|---|---|---|---|
| (0,0) | 0 | 1 | 1 |
| (0,4) | 2 | 1 | 3 |
| (2,0) | 2 | 1 | 3 |
| (2,4) | 2 | 1 | 3 |
| (1,2) | 1 | 0 | 1 |
(1,2) 的马只能走 1 步，它 1 步能到的格子只有 (0,0)、(0,4)、(2,0)、(2,4) 四个（其余越界）；(0,0) 的马 1 步能到 (1,2) 与 (2,1)。两匹马都能到的格子里合计最小是 1：(0,0)（(1,2) 的马跳过去，(0,0) 的马不动）与 (1,2)（(0,0) 的马跳过去）都是 1，其余三格都是 3 → 输出 1。
两个边界：到不了同一格 / 只有一匹马
3×4 棋盘 1 . . 1 / . . . . / . . . .：两匹马各只能走 1 步，可达格分别是 {(1,2),(2,1)} 与 {(1,1),(2,2)}，没有公共格 → 输出 0
1×1 棋盘只有一匹马 2：它自己所在格合计 0 → 输出 0（与「不可以」同为 0，题面如此）复杂度：每匹马一次 BFS O(mn)，h 匹马 O(h·mn)，再逐格求和 O(h·mn)。步数上限用「最多扩 k 层」截止：while q and level < limit。
08 / 从步骤到程序
四道题的完整参考程序，每一步落在哪几行
先自己写完并提交一次，再展开对照。
| 题 | 第 0 层 | 过滤 + 标记 | 答案 |
|---|---|---|---|
| P3702 | 所有 YES q.append；数 NO 得 todo | grid[nr][nc] == "NO" → 改成 YES、todo -= 1、入队 | days if todo == 0 else -1 |
| P3708 | dist[0][0] = 0 | dist[nr][nc] == -1 and abs(高度差) <= k → dist = dist + 1 | 结束后逐格选最高、同高步数短；无更高格 → 0 0 |
| P3700 | 唯一信号源 | grid[nr][nc] == 0 → 写入当前强度；强度为 0 前 break | grid[ti][tj] |
| P3706 | 每匹马各一次 | 八方向；level < limit | 逐格求和，-1 表示有马到不了；取最小，否则 0 |
展开完整参考程序 1：P3702 火星改造（先自己写完并提交一次，再展开对照）
完整程序：P3702（标准输入 → 标准输出）
Pythonimport sys
from collections import deque
grid = [line.split() for line in sys.stdin.read().split("\n") if line.strip()] # 行数未知：读到文件尾
rows, cols = len(grid), len(grid[0])
q = deque()
todo = 0 # 还没改造的 NO 格数
for r in range(rows):
for c in range(cols):
if grid[r][c] == "YES":
q.append((r, c)) # 所有宜居区都是第 0 层
elif grid[r][c] == "NO":
todo += 1
days = 0
while q and todo: # 队列非空且还有待改造格
for _ in range(len(q)): # 只处理当前这一层
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "NO":
grid[nr][nc] = "YES" # 入队即标记：直接把格子改成 YES
todo -= 1
q.append((nr, nc))
days += 1 # 走完一层，过一天
print(days if todo == 0 else -1)自测建议：题面示例（输出 1）、第 04 节 3×3（输出 2）、无法全覆盖的例子（输出 -1）、没有 NO（输出 0）、没有源点却有 NO（输出 -1）。
展开完整参考程序 2：P3708 周末爬山
完整程序：P3708（标准输入 → 标准输出）
Pythonimport sys
from collections import deque
data = sys.stdin.read().split()
m, n, k = int(data[0]), int(data[1]), int(data[2])
vals = [int(x) for x in data[3:3 + m * n]]
grid = [vals[i * n:(i + 1) * n] for i in range(m)]
dist = [[-1] * n for _ in range(m)] # -1 = 未到达；到达时记最短步数
dist[0][0] = 0
q = deque([(0, 0)])
while q:
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == -1 and abs(grid[nr][nc] - grid[r][c]) <= k:
dist[nr][nc] = dist[r][c] + 1 # 第一次到达就是最短步数（每步代价相同）
q.append((nr, nc))
best_h, best_d = grid[0][0], 0 # 与题目页参考题解一致：只有比起点更高的格才算「爬到的山峰」
for r in range(m):
for c in range(n):
if dist[r][c] >= 0 and (grid[r][c] > best_h or (grid[r][c] == best_h and grid[r][c] > grid[0][0] and dist[r][c] < best_d)):
best_h, best_d = grid[r][c], dist[r][c]
if best_h > grid[0][0]:
print(best_h, best_d)
else:
print(0, 0) # 没有比起点更高的可达格：高度和步数都输出 0自测建议：第 05 节手算图（输出 4 4）与两个边界例。「没有比起点更高的可达格 → 0 0」按题目页参考题解处理（起点本身是最高时也输出 0 0）。
展开完整参考程序 3：P3700 计算网络信号（进阶）
完整程序：P3700（标准输入 → 标准输出）
Pythonimport sys
from collections import deque
data = sys.stdin.read().split()
m, n = int(data[0]), int(data[1])
vals = [int(x) for x in data[2:2 + m * n]]
ti, tj = int(data[2 + m * n]), int(data[3 + m * n])
grid = [vals[i * n:(i + 1) * n] for i in range(m)]
q = deque()
for i in range(m):
for j in range(n):
if grid[i][j] > 0:
q.append((i, j)) # 唯一的信号源
strength = grid[q[0][0]][q[0][1]]
while q:
strength -= 1 # 每向外一层衰减 1
if strength == 0:
break # 衰减到 0 不再扩散
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0: # 只走空旷且未赋值的格
grid[nr][nc] = strength # 直接把信号值写进网格，同时起到「已访问」标记的作用
q.append((nr, nc))
print(grid[ti][tj])自测建议：题面示例（输出 2）、目标是信号源本身（输出 4）、超出衰减范围的 (5,0)（输出 0）。
展开完整参考程序 4：P3706 跳马问题（进阶）
完整程序：P3706（标准输入 → 标准输出）
Pythonimport sys
from collections import deque
MOVES = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)) # 马的八个方向
lines = [line for line in sys.stdin.read().split("\n") if line.strip()]
m, n = int(lines[0].split()[0]), int(lines[0].split()[1])
grid = [lines[1 + i].split() for i in range(m)]
def horse_steps(sr, sc, limit): # 这匹马到每个格子的最少步数；超过 limit 或到不了记 -1
steps = [[-1] * n for _ in range(m)]
steps[sr][sc] = 0
q = deque([(sr, sc)])
level = 0
while q and level < limit: # 最多扩 limit 层
level += 1
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in MOVES:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and steps[nr][nc] == -1:
steps[nr][nc] = level
q.append((nr, nc))
return steps
total = [[0] * n for _ in range(m)] # 每个格子：所有马步数之和；-1 = 有马到不了
for r in range(m):
for c in range(n):
if grid[r][c] != ".":
steps = horse_steps(r, c, int(grid[r][c]))
for x in range(m):
for y in range(n):
if total[x][y] == -1 or steps[x][y] == -1:
total[x][y] = -1
else:
total[x][y] += steps[x][y]
best = min((total[x][y] for x in range(m) for y in range(n) if total[x][y] != -1), default=None)
print(best if best is not None else 0)自测建议：第 07 节手算例（输出 1）、到不了同一格的例子（输出 0）、第 10 节练习 5（输出 2）。
09 / 边界、反例与复杂度
错误做法在具体输入上各输出什么
下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。
| 错误做法 | 输入 | 错误输出 | 正确输出 | 判题结果 |
|---|---|---|---|---|
| P3702 每出队一个点就加一天 | 第 04 节 3×3 | 5 | 2 | 答案错误（WA） |
| P3702 只让第一个 YES 入队（单源） | 第 04 节 3×3 | 4 | 2 | 答案错误（WA） |
| P3702 循环条件只看队列非空（待改造归零后多算一天） | 第 04 节 3×3 | 3 | 2 | 答案错误（WA） |
| P3702 结束后不判剩余待改造格 | YES NA NO / NA NA NA / NO NO NO | 1 | -1 | 答案错误（WA） |
| P3702 出队才标记 | 大网格 | 同一格重复入队、待改造格数被多减 → 天数偏小或提前结束 | — | 答案错误（WA）或超时（TLE） |
| P3708 漏掉高度差 ≤ k 的过滤 | 第 05 节 3×3 | 5 2 | 4 4 | 答案错误（WA） |
| P3708 同高用 ≥ 更新（后到达的覆盖先到达的） | 2 3 3 / 0 3 1 / 1 1 3 | 3 3 | 3 1 | 答案错误（WA） |
| P3700 强度衰减到 0 不停 | 题面示例地图，求 (5,0) | -2 | 0 | 答案错误（WA） |
| P3706 马的步数上限没生效 | 3 4 / 1 . . 1 / . . . . / . . . . | 5 | 0 | 答案错误（WA） |
| 用 list.pop(0) 当队列 | 500×500 地图 | 结果正确但每次出队 O(n) | 同左 | 超时（TLE） |
第一行的 5：3×3 里共有 6 个 N 要被改造，但按「每出队一点加一天」，第 0 层两个源点各加一次、之后每个被改造格出队再加，得到 5。第二行的 4：只从 (0,0) 扩散，(2,2) 附近的格子要多走几层。
| 做法 | 时间 | 500×500 时 |
|---|---|---|
| BFS，入队即标记 | O(rows×cols) | ≈ 2.5×10⁵ 次入队 |
| BFS，出队才标记 | 最坏每格入队 4 次 | ≈ 10⁶ 次入队，且计数类题答案错 |
| DFS 递归 | O(rows×cols) 但递归深度可达格数 | 全可走时约 2.5×10⁵ 层 → 递归上限错误 |
list.pop(0) 当队列 | 每次出队 O(队列长) | 超时 |
10 / 渐进练习与参考答案
跟做 → 改一个条件 → 独立实现 → 迁移
每题先在纸上或文件里做完，再展开答案。
练习 1（跟做）：按第 04 节表的格式，对网格 YES NO NO NO / NA NA NA NO / NO NO NO NO 逐天列出被改造的格子与剩余待改造数，写出输出。
展开练习 1 答案
源点只有 (0,0)，待改造 8。第 1 天：(0,1) → 剩 7；第 2 天：(0,2) → 6；第 3 天：(0,3) → 5；第 4 天：(1,3) → 4；第 5 天：(2,3) → 3；第 6 天：(2,2) → 2；第 7 天：(2,1) → 1；第 8 天：(2,0) → 0。输出 8——一条绕过死亡区的长路，每天只前进一格。
练习 2（改一个条件）：P3702 改成八方向扩散（含对角），第 04 节的 3×3 网格几天完成？方向数组怎么写？
展开练习 2 答案
方向数组加上四个对角 (1,1)、(1,−1)、(−1,1)、(−1,−1)。第 1 天：(0,0) 改造 (0,1)、(1,1)；(2,2) 改造 (1,2)、(2,1)、(1,1)（已改）→ 剩 (0,2)、(2,0)；第 2 天：(0,1) 改造 (0,2)，(2,1) 改造 (2,0) → 0。仍是 2 天，但第 1 天多改了 (1,1)。只改方向数组，其余代码不动。
练习 3（改一个条件）：P3708 改成「只能往不低于当前格高度的方向走」（不再限制高度差）。过滤条件怎么写？对第 05 节的地图，最高峰和步数是多少？
展开练习 3 答案
过滤改成 grid[nr][nc] >= grid[r][c]。地图 0 1 2 / 1 5 3 / 2 3 4：从 (0,0)=0 可到 (0,1)=1、(1,0)=1；再到 (0,2)=2、(1,1)=5、(2,0)=2；(1,1)=5 之后只能去不低于 5 的格——没有；(0,2)=2 → (1,2)=3 → (2,2)=4；(2,0)=2 → (2,1)=3 → (2,2)=4。最高 5 在 (1,1)，步数 2 → 输出 5 2。
练习 4（独立实现）：完成「代码自测」的 spread_days，再加一条断言：没有源点却有 N 的网格 [list("NN")] 应返回 −1。
展开练习 4 答案
spread_days 的参考实现（自带断言）
Pythonfrom collections import deque
def spread_days(grid):
rows, cols = len(grid), len(grid[0])
q = deque()
todo = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "Y":
q.append((r, c)) # 所有源点都是第 0 层
elif grid[r][c] == "N":
todo += 1
days = 0
while q and todo: # 待改造格归零就停，不多算一天
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "N":
grid[nr][nc] = "Y" # 入队即标记
todo -= 1
q.append((nr, nc))
days += 1
return days if todo == 0 else -1
# 手推过的 3×3：第 1 天改 3 格、第 2 天改 3 格
assert spread_days([list("YNN"), list("XNN"), list("NNY")]) == 2
# 一个 N 被 X 围死
assert spread_days([list("YXN"), list("XXX"), list("NNN")]) == -1
# 没有 N，第 0 天就完成
assert spread_days([list("YY"), list("YY")]) == 0
# 没有源点、却有 N
assert spread_days([list("NN")]) == -1四条断言覆盖：3×3 两天、被围 −1、没有 N 的 0 天、没有源点的 −1。循环条件 while q and todo 同时挡住「多算一天」与「没有源点」。
练习 5（迁移）：不运行程序，对 P3700 题面示例地图手算 (5,0) 与 (0,0) 的信号值；再对 P3706 的 3×5 棋盘 1 . . . 1 / . . . . . / . . . . .（两匹马各最多 1 步）算出输出。
展开练习 5 答案
(5,0)：从 (2,3) 出发，最近路径要绕过 (2,2) 与 (4,4)，到 (5,0) 至少 6 步，而强度 4 只能扩 3 层 → 未覆盖 → 0。(0,0)：距离 5 步 → 0。跳马：(0,0) 的马 1 步可到 (1,2)、(2,1)；(0,4) 的马 1 步可到 (1,2)、(2,3)；公共格 (1,2) 合计 1 + 1 = 2 → 输出 2。
11 / 读题要求与复习自评
四道题的要求对照，以及完成本课之后怎么复习
提交前把下表过一遍；题目页的题面与样例是最终依据。
| 项目 | P3702 | P3708 | P3700 | P3706 |
|---|---|---|---|---|
| 输入 | 若干行 YES/NO/NA（行数不给） | m n k；m 行高度 | m n；一行 m×n 个值；目标 i j | m n；m 行棋盘（数字或 .） |
| 输出 | 天数；无法全覆盖 -1 | 最高高度 最短步数；无更高格 0 0 | 目标格信号值；未覆盖 0 | 最小总步数；不可行 0 |
| 第 0 层 | 所有 YES | (0,0) | 唯一信号源 | 每匹马 |
| 过滤 | 邻格 NO | 高度差 ≤ k | 空旷格、强度 > 0 | 八方向、步数 ≤ 上限 |
| 数据范围 | 题目页为准 | m、n ≤ 500，k < 5 | 题目页为准 | 题目页为准 |
| 样例 | 题面 3×3 → 1 | 自拟 3 3 1 地图 → 4 4 | 题面 6×5 求 (1,4) → 2 | 参考题解 3×5 两匹马 → 1 |
需要对照解法时，展开本课第 08 节的完整参考程序；题目页另有思路与参考代码，可在题目页查看。完成条件：本课算完成 = P3702、P3708 两道必做题都通过判题，并勾选全部六条「学习完成检查」；六条检查是自评，勾选不改变题目的通过（AC）状态；进阶练习与复习题单独统计，不影响完成状态。复习时用三个问题自测：① 不看正文，写出层数统计的循环骨干并说出为什么先取 len(q)；② 不看表格，重推第 04 节 3×3 网格的两天；③ 说出 P3702 的 -1 为什么看待改造格数而不是队列。答不出哪一条，就回到对应的节重读，再做第 10 节对应的练习。
基础加练（选做）
同一主题的 2 道基础题
这组题目采用标准输入输出（ACM 模式）：程序从标准输入读取数据、把结果写到标准输出。它们难度低于必做题，适合在必做题之前热身，或在未通过时回来巩固；不计入本课完成标准。每道题给出练习重点、完成标准与提示；已在本站通过的题目会直接显示为已通过。
12 / 练习
按顺序完成本课的任务
必做题已通过 0/2 道；进阶练习已通过 0/2 道
多源扩散的天数（spread_days）
代码自测自主练习练习重点：源点全部入队、入队即标记、整层出队计天数；预计用时：15 分钟
完成标准：能解释 -1 的判定为什么要根据剩余待改造格数，而不是「队列空了」
需要时查看提示
先数清待改造格数 todo（N 的个数）；每改造一格减一。循环条件是「队列非空且待改造格数大于 0」：待改造格数归零后不要再多算一天。参考实现在第 10 节练习 4 的展开区。
自测代码（复制到你的代码文件中运行，检查输出是否一致）
from collections import deque
def spread_days(grid):
# 你来写：多源 BFS，返回全部 N 变 Y 的天数；无法全覆盖返回 -1
...
# 手推过的 3×3：第 1 天改 3 格、第 2 天改 3 格
assert spread_days([list("YNN"), list("XNN"), list("NNY")]) == 2
# 一个 N 被 X 围死
assert spread_days([list("YXN"), list("XXX"), list("NNN")]) == -1
# 没有 N，第 0 天就完成
assert spread_days([list("YY"), list("YY")]) == 0P3702 · 火星改造
必做任务 1练习重点：多源初始化 + 层数即天数 + 无法全覆盖输出 -1；预计用时：25 分钟
完成标准：能整段说出「为什么所有源点要同时入队、天数为什么等于层数」
需要时查看提示
读入的 YES/NO/NA 是字符串，行数不给、读到文件尾。没有 NO 时答案是 0，不要让循环体误加一天；结束后仍有待改造格则输出 -1。第 04 节把题面示例逐天列出。
P3708 · 周末爬山
必做任务 2练习重点：高度差 ≤ k 的过滤 + 可达集合里选最高、同高选步数短；预计用时：25 分钟
完成标准：能解释「第一次到达即最短步数」成立的前提
需要时查看提示
从 (0,0) 起单源 BFS，记录每个可达格的层数。答案在 BFS 结束后统一选：高度优先、同高比步数；没有比起点更高的可达格时高度和步数都输出 0（题目页参考题解如此处理，起点本身是最高时也输出 0 0）。第 05 节有逐层表。
P3700 · 计算网络信号
进阶练习 1进阶练习练习重点：信号值 = 源强度 − 层数；衰减到 0 停止扩散；预计用时：20 分钟
完成标准：能说出为什么阻隔物不需要特殊算法，绕行是 BFS 的自然行为
需要时查看提示
一行 m×n 个值先折成网格。强度每层减 1，减到 0 就停止扩散；目标位置不可达（被阻隔物围住或超出衰减范围）时保持 0。第 06 节把题面示例的整张信号图算了出来。
P3706 · 跳马问题
进阶练习 2进阶练习练习重点：每匹马各自 BFS（马步八方向 + 步数上限），汇合点取总和最小；预计用时：30 分钟
完成标准：能说出「所有马到同一格」为什么是逐马 BFS 再按格求和
需要时查看提示
对每匹马跑一次 BFS 得到它到每个格子的最少步数（超过它的步数上限记为不可达）；答案 = 在所有格子上求「每匹马步数之和」的最小值，存在马到不了的格子就跳过该格；没有可行格输出 0。第 07 节有两匹马的手算。
提交结果
提交结果说明与处理方法
- WA
答案错误
优先检查三处：天数在错误时机自增（每出队一个点就 +1）、漏了部分源点、无法全覆盖时没输出 -1——第 09 节的表给出了每种错误的具体输出
- RE
运行错误
访问 (nr, nc) 前先判越界；YES/NO/NA 是字符串，不要当单字符比较；P3700 的一行输入要先折成网格
- TLE
超时
出队才标记导致重复入队；队列用了列表头部弹出（list.pop）代替双端队列（deque）
- AC
通过
再测没有 N、单格网格、源点被 X 围住三个边界；想想 DFS 在多深的网格会超过递归上限
13 / 学习完成检查
本课学习完成检查
完成本课需要：必做题全部通过，并勾选本课的全部学习完成检查；进阶练习、基础加练与复习题单独统计，不影响完成状态。登录后，勾选记录会保存到账号，并更新课程总览的完成状态。