GESP6级C++考试语法知识（泛洪算法（Flood Fill））

图像里的魔法——泛洪算法（Flood Fill）

一、先讲一个生活中的故事

小明有一张黑白地图：

########
#……#
#.####.#
#.#..#.#
#……#
########

其中：

• # 表示墙

• . 表示空地

现在小明拿着一桶颜料：

点击一个地方
↓

把和它连在一起的所有空地染成红色

这是不是很像：

画图软件里的“油漆桶工具”？

比如：

你点击一个区域：

……..
..####..
..#..#..
..####..
……..

油漆会自动扩散：

RRRRRRRR
RR####RR
RR#..#RR
RR####RR
RRRRRRRR

这个过程，就是：

Flood Fill（泛洪算法）

二、泛洪算法解决什么问题？

一句话：

从一个点出发，把所有“连通”的相同区域找出来。

关键词：

1. 从一个点开始

例如：

(2,3)

↓

2. 向四周扩散

看看：

上
下
左
右

↓

3. 如果符合条件，继续扩散

像水流一样：

↑
|
← ← 起点 → →
|
↓

三、二维地图怎么表示？

计算机里面：

地图就是二维数组。

例如：

1 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 0 0 0 1
1 1 1 1 1

C++：

int mp[5][5];

表示：

mp[行][列]

例如：

mp[2][3]

就是：

第2行，第3列。

四、泛洪算法的核心思想

假设：

0代表土地

1代表障碍

地图：

0 0 0 1 1
0 0 1 1 1
0 0 0 0 1
1 1 0 0 0

从：

(0,0)

开始。

我们想：

把所有和它连接的0变成2。

过程：

第一步

染当前位置：

2 0 0 1 1
0 0 1 1 1
0 0 0 0 1
1 1 0 0 0

然后检查：

上
下
左
右

第二步

向右：

2 2 0 1 1
0 0 1 1 1
0 0 0 0 1
1 1 0 0 0

继续：

2 2 2 1 1
0 0 1 1 1
0 0 0 0 1
1 1 0 0 0

直到所有连接区域完成。

五、DFS实现泛洪算法（最经典）

1. 定义方向

因为只能走：

上
下
左
右

所以：

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

解释：

第0种：

x-1,y

向上

第1种：

x+1,y

向下

第2种：

x,y-1

向左

第3种：

x,y+1

向右

六、写DFS函数

模板：

void dfs(int x,int y)
{

}

表示：

现在站在：

(x,y)

这个位置。

第一步：染色

为什么？

因为：

如果不标记，

会无限循环。

例如：

A -> B

B -> A

A -> B

…

所以：

进入一个点：

马上标记。

代码：

mp[x][y]=2;

第二步：尝试四个方向

for(int i=0;i<4;i++)
{

}

第三步：计算新坐标

int nx=x+dx[i];
int ny=y+dy[i];

比如：

现在：

x=3
y=4

向上：

nx=2
ny=4

第四步：判断能不能走

需要满足：

条件1：

不能越界

例如：

-1行

不存在。

所以：

nx>=0

条件2：

必须是目标颜色

比如：

只能走0：

mp[nx][ny]==0

完整：

if(nx>=0&&nx<n
&&ny>=0&&ny<m
&&mp[nx][ny]==0)
{
dfs(nx,ny);
}

七、完整C++代码

题目：

把和起点连通的0全部变成2。

#include<iostream>
using namespace std;

int n,m;

int mp[100][100];

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

void dfs(int x,int y)
{

//1.染色
mp[x][y]=2;

//2.寻找四个方向
for(int i=0;i<4;i++)
{

int nx=x+dx[i];
int ny=y+dy[i];

//3.判断是否可以继续
if(nx>=0&&nx<n
&&ny>=0&&ny<m
&&mp[nx][ny]==0)
{
dfs(nx,ny);
}

}

}

int main()
{

cin>>n>>m;

for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mp[i][j];
}
}

int x,y;

cin>>x>>y;

dfs(x,y);

for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<mp[i][j]<<" ";
}

cout<<endl;
}

return 0;
}

八、学生最容易犯的3个错误

错误1：忘记标记

错误：

void dfs(int x,int y)
{

dfs(nx,ny);

}

没有：

mp[x][y]=2;

结果：

无限递归。

为什么？

例如：

A B
C D

A走B：

A→B

B又能走A：

B→A

死循环。

错误2：方向数组写错

很多孩子写：

int dx[4]={1,1,-1,-1};

这是什么？

变成：

↘
↙
↗
↖

走斜线。

如果题目要求上下左右：

必须：

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

错误3：边界忘记判断

例如：

第0行

再向上：

-1行

数组：

mp[-1][0]

非法。

程序可能：

• 崩溃

• 输出奇怪结果

九、DFS和BFS有什么区别？

泛洪算法有两种写法：

DFS

深度优先搜索：

像一个小朋友探险：

一直走到底

走不通回来

特点：

代码短。

适合：

• 区域染色

• 连通块

BFS

广度优先搜索：

像水波：

第一圈

第二圈

第三圈

使用：

队列 queue。

适合：

• 最短距离

• 迷宫最短路

十、信奥赛中的经典应用

泛洪算法非常重要。

以后会遇到：

1. 统计岛屿数量

例如：

11000
11000
00100
00011

有几个岛？

答案：

每找到一个1：

DFS染掉。

2. 迷宫连通性

判断：

起点能不能到终点

3. 最大区域面积

例如：

0 1 1
1 1 0
1 0 0

找最大连通块。

4. 填充地图

类似：

画图软件油漆桶

十一、给同学们总结一句话

泛洪算法就是：
从一个位置出发，像水一样向四周流动，把所有能够到达的地方全部处理一遍。

记住三个关键：

第一：

二维数组表示地图。

第二：

DFS/BFS负责扩散。

第三：

一定要：

走一步，标记一步。

对于信奥赛学生来说，泛洪算法其实是进入 DFS搜索、连通块、图论 的第一座桥梁。掌握它以后，后面的 迷宫问题、岛屿问题、图的遍历、BFS最短路 都会顺畅很多。