PYTHON LESSON 086
迷宫探险
掌握深度优先搜索的“标记 + 扩展”套路，会用 DFS 统计迷宫可达区域。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 方向数组 dirs = [(-1,0),(1,0),(0,-1),(0,1)]
- visited[r][c] 访问标记
- 递归 dfs(r, c)：先标记，再向四个方向钻
01 · 核心概念
深度优先搜索 DFS
深度优先搜索 DFS：深度优先搜索像一位倔强的探险家：每到一个岔路口，挑一条路一直走到死胡同，才退回上一个岔口换下一条。配合粉笔（visited 标记）保证同一个格子绝不走两遍。
GESP Python 6 级 · 深度优先搜索 DFS有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
方向数组 dirs = [(-1,0),(1,0),(0,-1),(0,1)]先准确读出这条写法的结构与作用。
visited[r][c] 访问标记换一组最小数据，手工推演一次结果。
递归 dfs(r, c)：先标记，再向四个方向钻再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 迷宫探险：深度优先搜索（DFS）
maze = [
"S..#",
"##.#",
"...#",
".#..",
".##E",
]
rows = len(maze)
cols = len(maze[0])
visited = [[False] * cols for _ in range(rows)]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上、下、左、右
order = []
def dfs(r, c):
visited[r][c] = True
order.append((r, c))
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if maze[nr][nc] != "#" and not visited[nr][nc]:
dfs(nr, nc)
dfs(0, 0) # 从起点 S 出发
print("DFS 一共探索了", len(order), "个格子")
print("前 6 个到达的格子：", order[:6])
if maze[order[-1][0]][order[-1][1]] == "E":
print("最后一个格子正好是出口 E，探险成功！")
else:
found = any(maze[r][c] == "E" for r, c in order)
print("出口在可达范围内吗？", found)DFS 一共探索了 12 个格子 前 6 个到达的格子： [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2)] 出口在可达范围内吗？ True
坐标按（行，列）记录，从 0 开始；DFS 一头扎到底再回头，所以第 8 步就到过出口了。
04 · 逐步理解
每一步只解决一个问题
- 01
DFS 的探险策略
深度优先搜索像一位倔强的探险家：每到一个岔路口，挑一条路一直走到死胡同，才退回上一个岔口换下一条。配合粉笔（visited 标记）保证同一个格子绝不走两遍。
- 02
方向数组：四方向一招鲜
上下左右四个方向不用写四段几乎一样的代码：把 (-1,0)、(1,0)、(0,-1)、(0,1) 装进列表，一个 for 循环轮流取出 dr、dc，新坐标就是 r+dr、c+dc。这是网格类搜索的标准动作。
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] for dr, dc in dirs: nr, nc = r + dr, c + dc - 03
边界检查两件事
扩展新格子前必须确认：① 坐标没有越出迷宫边界（0 <= nr < rows 且 0 <= nc < cols）；② 不是墙壁、没有访问过。漏掉任何一条，程序不是崩溃就是死循环。
if 0 <= nr < rows and 0 <= nc < cols: if maze[nr][nc] != "#" and not visited[nr][nc]: - 04
先标记，再递归
dfs 一进函数立刻 visited[r][c] = True，然后才向四周递归。顺序不能反：如果递归回来才标记，相邻两个格子会互相把对方当成“没去过”，在两个格子之间无限打转。
def dfs(r, c): visited[r][c] = True order.append((r, c)) - 05
用 any 做总结
any(...) 表示“任意一个成立就成立”。出口 E 是否在探索过的格子里，一行就能回答。配合生成器表达式，不用写循环也能表达“是否存在”。
found = any(maze[r][c] == "E" for r, c in order) - 06
DFS 的脾气
把 order 全部打印出来你会发现：DFS 第 8 步就撞到了出口，却没有停下来，而是继续把另一条岔路也走完。DFS 只保证“走遍”，不保证“最近”——最短路线是下一课 BFS 的绝活。迷宫很大时记得 sys.setrecursionlimit 或改用显式栈。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，看 DFS 探索了多少格子
- 2打印完整探索顺序，体会“一条路走到底”
- 3封死一堵墙，看可达格子怎么变
- 4对比 DFS 顺序和“水波扩散”的顺序有什么不同
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
程序组织函数、参数、返回值与作用域用明确的输入、输出和职责拆分程序，理解参数绑定、作用域、递归与可变对象。＋
正式定义
函数把一段可复用行为绑定到名字。调用时实参按规则绑定到形参，函数执行后用 return 交回结果；没有显式 return 时返回 None。名字解析遵循局部、闭包、全局、内置的 LEGB 顺序。
必须掌握
- 位置参数先于关键字参数；默认值在 def 执行时创建一次，不应直接使用可变容器作默认值。
- return 立即结束当前函数；return a, b 实际返回一个元组。
- 函数内赋值默认创建局部变量；global 声明模块级名字，nonlocal 声明最近外层函数名字。
- 传参传递的是对象引用；函数是否影响调用方取决于对象是否可变以及函数是否原地修改。
- 递归必须有可到达的终止条件，并要考虑调用深度、重复子问题和栈空间。
- 纯函数更容易测试；把输入输出、计算逻辑和全局状态分开能显著减少错误。
常见误区
- 可变默认参数在多次调用间共享
- 忘记 return 导致得到 None
- 局部变量遮蔽全局同名变量
- 递归没有缩小问题规模
适用边界
- lambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
- 装饰器、生成器和闭包属于函数模型的进阶应用，应在基本参数与作用域稳定后学习。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
完成检查