从「填涂颜色」看漫水填充（Flood Fill）算法与逆向思维
在图论和算法竞赛中，经常会遇到一类'染色'或'寻找连通块'的问题。解决这类问题的一把利器就是 Flood Fill（漫水填充）算法。
本文将以洛谷的一道经典题目 P1162 填涂颜色 为例，详细解析 Flood Fill 算法的原理，以及在算法解题中非常重要的一种技巧——逆向思维。
一、题目回顾：洛谷 P1162 填涂颜色
题目描述：
由数字 0 组成的方阵中，有一任意形状的由数字 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2。
输入样例（简略）：
6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1
输出样例：
0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1
*注：闭合圈不一定是环形的，但保证圈内 0 是连通的。
二、核心算法：什么是 Flood Fill（漫水填充）？
听名字可能觉得有些抽象，但其实这个概念在日常软件中随处可见。 打开 Windows 自带的'画图'软件，里面有一个'油漆桶'工具。当使用线条画了一个封闭的圆，然后用油漆桶往里面点击一下，整个圆就被涂满了颜色，而圆的外部则毫无影响。
Flood Fill 算法的本质，就是这个'油漆桶'。 它的基本思想是：从一个起始节点开始，把附近所有相连的、符合相同条件的节点提取出来，并进行状态修改（比如染色）。 通常，Flood Fill 可以通过 DFS（深度优先搜索） 或 BFS（广度优先搜索） 来实现。
三、思路解析：寻找'内'还是寻找'外'？
回到这道题，题目要求把 1 围起来的内部的 0 变成 2。
❌ 常规思维（容易碰壁）
如果直接去寻找'闭合圈内的 0'，会发现非常困难：
- 闭合圈形状是不规则的，程序很难直观地判断当前的
0究竟是在圈内还是圈外。 - 如果从任意一个
0开始搜索，碰到1停止，它到底是被包围的，还是只是碰巧靠着墙？需要加入大量复杂的特判。
✅ 逆向思维（巧妙破局）
既然找'内部'太难，那么不妨转换视角，寻找'外部'。
闭合圈内部的 0 是被 1 死死围住的，而外部的 0 有一个极其明显的特征：它们一定能和矩阵的四条边界（上下左右）连通！
于是，完美的破局思路诞生了：
- 先发制人（全盘染色）：在读取输入时，先把所有的
0都假设为闭合圈内部，全部强行赋值为2。 - 边缘突破（漫水填充）：从矩阵的四条边界（第一行、最后一行、第一列、最后一列）开始遍历。只要发现边缘有
2，就说明这是真正的'外部区域'。从这个边缘的2开始，使用 Flood Fill 算法（DFS），把和它连通的所有2统统'洗'回0。 - 水落石出：当算法结束时，留在矩阵里的
2，就是那些连边缘都渗透不进去的区域——也就是真正的'闭合圈内部'！
四、代码实现与细节剖析
基于上述思路，采用 DFS 来实现 Flood Fill。下面是结构清晰、易于理解的 C++ 代码实现：
