泛洪算法
1. 泛洪算法（Flood Fill）
泛洪算法是一种 从某个起点开始，把相连区域全部搜索出来 的算法。
核心思想：
从一个点出发，把所有能连通的同类位置全部扩散访问。
名字来源于现实中的“灌水”：
- 水从一个点倒下去
- 会向四周蔓延
- 直到无法继续扩散
这就是泛洪算法。
2. 泛洪算法解决什么问题
常见用途：
- 统计岛屿数量
- 求连通块大小
- 迷宫区域搜索
- 图片染色
- 判断区域是否封闭
- 地图块搜索
例如地图：
从某个 1 出发，可以找到一整块连在一起的区域。
3. 本质是什么
泛洪算法本质就是：
DFS 或 BFS 搜索二维网格中的连通区域。
也就是说，泛洪不是一种独立数据结构，而是一种应用方式。
通常使用：
- DFS（递归写法简单）
- BFS（队列写法稳定）
与BFS的本质区别 🧠 算法知识卡：泛洪算法 (Flood Fill) vs. DFS 一句话概括 泛洪算法是“任务目标”（把这片涂色），DFS 是“达成手段”（一条路走到黑）。 在网格连通性问题中，DFS 是实现 Flood Fill 最常用的“工具”之一。 📊 核心维度对比
| 维度 | 泛洪算法 (Flood Fill) | 深度优先搜索 (DFS) |
|---|---|---|
| 本质属性 | 区域处理算法（关注“结果”） | 图遍历策略（关注“过程”） |
| 应用对象 | 二维网格、位图、像素矩阵 | 任意图结构、树、社交网络、逻辑状态空间 |
| 状态记录 | 直接修改原数据（如：将 1 染成 2） |
使用辅助数组（如：vis[N]） |
| 回溯需求 | 极少需要（染完色不需要恢复原状） | 经常需要（寻找路径、全排列等需撤销操作） |
🛠️ 代码逻辑拆解
Flood Fill 模式：侧重属性过滤
* 口诀：先写“死”，再写“活”。
* 逻辑步序：
1. 边界检查：坐标是否出界？
2. 属性检查：颜色/高度是否符合填充要求？
3. 状态修改：立即改变当前点状态（避免死循环）。
4. 递归扩散：向 4 或 8 个方向蔓延。
标准 DFS 模式：侧重逻辑跳转
* 口诀：标记访问，递归邻居。
* 逻辑步序：
1. 标记当前点：vis[u] = true。
2. 遍历邻接点：从邻接表或矩阵中找邻居。
3. 判断后进入：仅当邻居未被访问过，才发起下一层递归。
“DFS 告诉你怎么走，Flood Fill 告诉你把走过的地方变成什么样。”
4. 四方向移动
在网格题中，经常只能上下左右移动。
代码常写成：
这样循环枚举四个方向。
5. DFS 泛洪模板
void dfs(int x, int y)
{
vis[x][y] = true;
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(合法 && 未访问 && 可进入)
{
dfs(nx, ny);
}
}
}
核心流程：
- 标记当前点已访问
- 向四周扩散
- 把整块区域全部搜完
6. 经典例题：统计岛屿数量
地图：
其中相连的 1 算一座岛。
做法：
- 枚举每个位置
- 遇到没访问过的
1 - 岛屿数 +1
- 对该点做一次泛洪
这样整座岛都会被标记。
7. 代码示例（DFS）
#include <iostream>
using namespace std;
int n, m;
char g[105][105];
bool vis[105][105];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y)
{
vis[x][y] = true;
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m &&
!vis[nx][ny] && g[nx][ny] == '1')
{
dfs(nx, ny);
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> g[i];
int cnt = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(g[i][j] == '1' && !vis[i][j])
{
cnt++;
dfs(i, j);
}
}
}
cout << cnt;
}
8. BFS 泛洪
如果地图很大，递归可能爆栈，可以用 BFS。
核心思路：
- 起点入队
- 每次弹出一个点
- 扩展四周可走位置
这样也能搜完整块区域。
9. 常见题型
岛屿数量
求有多少块陆地。
最大连通块
求最大区域面积。
染色问题
把一块区域改成新颜色。
迷宫区域
统计能走到多少格。
封闭区域
是否被墙包围。
10. 常见错误
忘记标记访问
会无限递归或重复搜索。
越界判断错误
数组边界写错最常见。
方向写错
上下左右坐标加减混乱。
把每个点重复搜索
导致超时。
11. 如何判断使用泛洪
看到这些关键词：
- 相连
- 连通块
- 区域
- 岛屿
- 地图搜索
- 矩阵扩散
通常就考虑泛洪算法。
12. 一句话理解
泛洪算法 = 从一个点出发，把整片连通区域全部搜出来。
13. 总结
泛洪算法本质是网格 DFS / BFS。
标准流程：
- 找到起点
- 开始扩散
- 标记访问
- 搜完整个区域
这是二维地图题最常见的基础算法之一。