洛谷Flood Fill算法专项题单
一、基础应用
- P1162 填涂颜色
- 反向边界填充经典题，用DFS/BFS标记矩阵封闭区域
- 难度：普及-
-
链接：题目链接
-
P1506 拯救oibh总部
- 统计未被洪水淹没的独立连通块数量
- 关键：处理矩阵边界条件
- 难度：普及-
-
链接：题目链接
-
P1331 海战
- 检测船只形状是否合法（非相邻）
- 需结合Flood Fill进行连通块验证
- 难度：普及/提高-
- 链接：题目链接
二、连通块处理
- P1141 01迷宫
- 预处理连通块大小+记忆化查询
- 注意：交替通行规则（0/1相邻）
- 难度：普及/提高-
-
链接：题目链接
-
P1596 [USACO10OCT]Lake Counting S
- 八方向连通水坑统计
- 标准Flood Fill模板题
- 难度：普及-
- 链接：题目链接
三、进阶变形
- CF1114D Flood Fill
- 区间DP+Flood Fill思想
- 关键：合并相邻同色块的最小代价计算
- 难度：提高-
-
链接：题目链接
-
P5022 [NOIP2018]旅行
- 基环树上的Flood Fill应用
- 需特殊处理环上断边策略
- 难度：提高
- 链接：题目链接
四、特殊场景
- P3623 [APIO2008]免费道路
- 生成树+Flood Fill验证连通性
- 需处理必须保留的特殊边
- 难度：提高-
-
链接：题目链接
-
P6066 Watchcow S
- 有向图边遍历顺序控制
- 用Flood Fill实现欧拉回路构造
- 难度：普及+/提高-
- 链接：题目链接
配套资源
练习建议：
1. 先完成基础题（P1162/P1506）掌握模板
2. 再挑战连通块预处理（P1141/P1596）
3. 最后尝试结合其他算法的综合题（CF1114D/P5022）
