PYTHON LESSON 087
最短逃生路线
掌握 BFS 逐层扩展的过程，会用 dist 数组求无权图/网格中的最短步数。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- from collections import deque 双端队列
- queue.popleft() 队首出队
- dist[nr][nc] = dist[r][c] + 1 记录层数
01 · 核心概念
宽度优先搜索 BFS 求最短步数
宽度优先搜索 BFS 求最短步数：宽度优先搜索像往水面丢一颗石子：波纹一圈圈向外扩。第 1 圈是所有走 1 步能到的格子，第 2 圈是走 2 步能到的……出口第一次被波纹碰到时，用的步数一定最少。
GESP Python 6 级 · 宽度优先搜索 BFS有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
from collections import deque 双端队列先准确读出这条写法的结构与作用。
queue.popleft() 队首出队换一组最小数据，手工推演一次结果。
dist[nr][nc] = dist[r][c] + 1 记录层数再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 最短逃生路线：宽度优先搜索（BFS）
from collections import deque
maze = [
"S..#",
"##.#",
"...#",
".#..",
".##E",
]
rows = len(maze)
cols = len(maze[0])
dist = [[-1] * cols for _ in range(rows)] # -1 表示还没到过
dist[0][0] = 0
queue = deque([(0, 0)])
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if maze[nr][nc] != "#" and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
print("从 S 到 E 最少需要", dist[4][3], "步")
print("每个格子的步数地图（-1 表示到不了）：")
for row in dist:
print(row)从 S 到 E 最少需要 7 步 每个格子的步数地图（-1 表示到不了）： [0, 1, 2, -1] [-1, -1, 3, -1] [6, 5, 4, -1] [7, -1, 5, 6] [8, -1, -1, 7]
BFS 像水波一圈圈扩散，第一次漫到出口时的圈数就是最短步数。
04 · 逐步理解
每一步只解决一个问题
- 01
BFS 的扩散策略
宽度优先搜索像往水面丢一颗石子：波纹一圈圈向外扩。第 1 圈是所有走 1 步能到的格子，第 2 圈是走 2 步能到的……出口第一次被波纹碰到时，用的步数一定最少。
- 02
队列保证“先来先扩”
用 deque 当波纹的“候补名单”：起点先入队；每次 popleft 请出队首格子，把它能到的新格子加到队尾。先进先出，保证第 1 圈全部处理完才轮到第 2 圈。列表 pop(0) 很慢，竞赛统一用 deque。
from collections import deque queue = deque([(0, 0)]) r, c = queue.popleft() - 03
dist 数组身兼两职
dist 全初始化为 -1，既是“步数记录”又是“访问标记”：还是 -1 说明没到过，可以扩展；不是 -1 就跳过。一个数组顶两个用，是 BFS 的经典写法。
if maze[nr][nc] != "#" and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 queue.append((nr, nc)) - 04
入队时机 = 标记录时机
新格子一被发明就立刻写 dist 并入队，而不是等出队时才标记。否则同一个格子会被多个邻居重复入队，步数也会被覆盖出错。
dist[nr][nc] = dist[r][c] + 1 queue.append((nr, nc)) - 05
读懂步数地图
打印出的 dist 地图里，从任意格子出发沿着数字递减的方向走，就能一步步退回起点——这就是“还原最短路线”的方法。需要输出完整路径时，再记录每个格子的“上家”即可。
- 06
DFS 与 BFS 怎么选
只求“能不能到”“有多少连通区域”，DFS、BFS 都可以；求“最少几步”“最近距离”，无权图上必须 BFS。把同一座迷宫交给两种搜索，对比它们的探索顺序，是理解两者的最好实验。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，核对最短步数与步数地图
- 2把某个 -1 格子打通，看路线怎么变
- 3手画前 3 层扩散范围
- 4对比同一座迷宫里 DFS 和 BFS 找到出口的顺序
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
程序组织模块、导入与常用标准库正确导入模块，并按用途查找 math、random、statistics、collections、heapq、bisect 等标准工具。＋
正式定义
模块是可导入的 Python 代码单元，包把模块组织成层次。import 先加载模块并创建模块对象，再把名字绑定到当前命名空间；标准库随 Python 分发，不等于第三方包。
必须掌握
- import module 保留清晰命名空间；from module import name 只导入指定名字；避免 from module import *。
- math 提供 sqrt、floor、ceil、gcd、log、sin 等数学函数和 pi、e 等常量。
- random 用于伪随机模拟，不适合密码安全；需要安全随机时使用 secrets。
- collections.deque 适合双端队列，Counter 适合计数，defaultdict 可按工厂创建缺省值。
- heapq 实现最小堆，bisect 在已排序序列中二分定位，itertools 提供高效迭代组合工具。
- if __name__ == '__main__': 用来区分文件被直接运行还是被导入。
常见误区
- 文件名写成 math.py 导致遮蔽标准库
- import * 污染命名空间
- 把 random 当成加密随机数
- 没有理解工具的数据复杂度就盲目调用
适用边界
- 标准库非常大，本章覆盖课程会实际依赖的入口；具体函数签名应结合本站条目与运行时帮助查询。
- Turtle 需要图形窗口，本站文本判题环境不伪造其画布。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
完成检查