PYTHON LESSON 101
魔法填色桶
掌握泛洪算法“从一个点染色一整片”的机制，会统计连通块个数与最大连通块。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- BFS/DFS 从种子点向四连通蔓延
- 染色即标记：改字符或置 visited
- 外层扫描找下一个未染色的种子
01 · 核心概念
泛洪算法 flood fill
泛洪算法 flood fill：从一滴颜料（种子点）出发，把四连通能到的同类格子全部染色——这就是泛洪。它没有任何新语法，本质就是上一课的 BFS/DFS 搬到了网格地图上。
GESP Python 7 级 · 泛洪 flood fill有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
BFS/DFS 从种子点向四连通蔓延先准确读出这条写法的结构与作用。
染色即标记：改字符或置 visited换一组最小数据，手工推演一次结果。
外层扫描找下一个未染色的种子再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 魔法填色桶：泛洪 flood fill
from collections import deque
grid = [
list("...##"),
list(".#.##"),
list(".##.."),
list("....."),
]
rows = len(grid)
cols = len(grid[0])
print("填色前：")
for row in grid:
print("".join(row))
# 从 (0,0) 滴入颜料 *，向四连通区域蔓延
queue = deque([(0, 0)])
grid[0][0] = "*"
count = 1
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 and grid[nr][nc] == ".":
grid[nr][nc] = "*"
count = count + 1
queue.append((nr, nc))
print("填色后：")
for row in grid:
print("".join(row))
print("一共填充了", count, "个格子")填色前： ...## .#.## .##.. ..... 填色后： ***## *#*## *##** ***** 一共填充了 13 个格子
把“染过色”直接当作访问标记，连 visited 数组都省了。
04 · 逐步理解
每一步只解决一个问题
- 01
泛洪就是网格上的 BFS/DFS
从一滴颜料（种子点）出发，把四连通能到的同类格子全部染色——这就是泛洪。它没有任何新语法，本质就是上一课的 BFS/DFS 搬到了网格地图上。
- 02
染色即标记
把 grid[nr][nc] 从 "." 改成 "*" 的瞬间，这个格子就再也不会被重复处理——染色同时完成了标记。grid 是可变的列表的列表，所以可以原地修改；字符串不行，所以开头用 list("...") 拆开。
grid = [list("...##"), list(".#.##")] grid[0][0] = "*" - 03
种子入队时就染色
和 BFS 一样，格子在入队的那一刻就要染色，而不是等出队。否则同一个格子会被好几个邻居重复入队，计数翻倍。
grid[nr][nc] = "*" queue.append((nr, nc)) - 04
数连通块：外层扫描 + 内层泛洪
想知道整张图有几块互不相通的区域？双重循环扫描每个格子，发现一个没染色的空地就“区域数 + 1”，然后从它发起一次泛洪把整块染掉。扫完图，块数和每块大小都有了。
for i in range(rows): for j in range(cols): if grid[i][j] == ".": comps += 1 flood(i, j) - 05
泛洪的应用版图
数岛屿数量、求最大岛屿面积、棋盘被围住的区域、照片去背景……都是同一个模板。配套题目要求同时输出“块数”和“最大块的格子数”，数据到 1000×1000，记得用 deque 和快速读入。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，对比填色前后的地图
- 2换一个滴颜料的位置，看填充范围变化
- 3数一数图上有几块互不相通的区域
- 4想想棋盘图案下每个区域有多大
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
编码与文本字符串、转义、切片与格式化从不可变字符序列到检索、拆分、拼接、格式化和常用判断方法。＋
正式定义
str 是不可变的 Unicode 字符序列。下标访问单个字符，切片生成新字符串；任何看似“修改字符串”的方法都会返回新对象。
必须掌握
- 下标从 0 开始，负下标从末尾开始；切片 s[start:stop:step] 不包含 stop，step 不能为 0。
- 转义序列用于在字面量中表示换行、制表、引号、反斜杠或码点；原始字符串仍有末尾反斜杠限制。
- find 找不到返回 -1，index 找不到抛 ValueError；count 统计不重叠出现次数。
- split 把字符串拆成列表，join 用一个字符串连接可迭代对象中的字符串，strip 只删除两端字符。
- f-string 的格式说明可控制宽度、对齐、精度、进制和百分比；格式化不改变原值。
- isalpha/isdigit 等按 Unicode 定义，不只识别英文字母和 ASCII 数字。
常见误区
- 尝试 s[0] = 'A' 原地修改字符串
- 把 strip('ab') 误解为删除完整子串 'ab'
- find 返回 -1 后直接拿去当有效下标
- 把字节长度与字符长度混为一谈
适用边界
- 正则表达式不在低等级字符串必修范围，但复杂模式匹配时应使用 re，而不是堆叠大量 split/find。
- 面向用户的字符计数还可能涉及组合字符和字素簇，len 统计的是 Unicode 码点序列长度。
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 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。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。
完成检查