当前位置：首页 > news >正文

FloodFill算法

news 2026/8/27 12:55:29

1.前言

来看下图：

floodfill解决的是一个大区域里有很多小区域，找出性质相同的连通块(上下左右连)。做法无非是从左往右扫描过程中发现低谷的时候，来一次深度或宽度优先遍历，一个地方走不通回溯到上一个位置继续遍历。

2.图像渲染

733. 图像渲染 - 力扣（LeetCode）https://leetcode.cn/problems/flood-fill/description/看图：

深度优先遍历，以这个位置为起点开始上下左右扫描。当扫描到和我像素值相同的区域后，就递归进去，但递归前别忘了把这块区域改为新的像素。所以从这个位置开始的时候先把它改为2：

然后上下左右遍历。因为深搜，所以这有2种方向时先选1个方向走。假设这往上走，走上去后这个位置的值改为2，然后以它为起点上下左右搜索：

假设往左走：

走不了后回溯，最终回溯回去。虽然可以往左走，但往上走后左边已经修改过了，此时不能走了，递归结束。说个细节：如果new是1，这样第二个位置扩展时可能回去，所以1的情况判断了，直接返回。下面实现：

2.岛屿数量

200. 岛屿数量 - 力扣（LeetCode）https://leetcode.cn/problems/number-of-islands/description/如图：

找连通块的数量，就一行行的扫描，当扫到第一个1的时候就把以这个1相连的区域都标记一下：

此时相当于找到了一块陆地。继续扫描，碰到被标记过的1不做统计，扫到没标记过的1相当于此时又找到了一个连通块：

用变量记录后再把与这个1连接的岛屿记录一下，这样依次类推。如何做到标记呢？弄一个vis[][]标记数组就行了。下面来实现：

3.岛屿的最大面积

695. 岛屿的最大面积 - 力扣（LeetCode）https://leetcode.cn/problems/max-area-of-island/description/依次扫描，扫描到陆地后就由这个陆地开始来一次深度优先遍历。可以弄一个count，只要进入深度优先遍历一次就让count++，深度优先遍历结束后count就统计的是这块岛屿的面积。可再用 ret统计所有count里的最大值。下面来实现：

4.被围绕的区域

130. 被围绕的区域 - 力扣（LeetCode）https://leetcode.cn/problems/surrounded-regions/description/如图：

我们期望最终把绿框中的两个0变X就行。刚开始想到的策略是依旧扫描一下矩阵，当碰到0时就开始沿着点来一次深度优先遍历。但有些区域是不能改的，所以深度优先遍历碰到非法位置的时候就向上回溯，但这样代码很难写。我们要用正难则反的思想，先把和边界有关的区域处理一下：

剩下的自然是在内部的0。怎么处理边界呢？扫描边界，碰到0后来一次深度优先遍历，都标记一下(这可把它们处理为点)，接下来扫描时碰到点还原为 0，碰到0修改为X。下面实现：

5.太平洋大西洋水流问题

417. 太平洋大西洋水流问题 - 力扣（LeetCode）https://leetcode.cn/problems/pacific-atlantic-water-flow/description/这道题给了我们一个矩阵，这个矩阵相当于一个陆地。这个陆地被两个洋包围，其中左以及上代表太平洋，右以及下代表大西洋。这个陆地上有很多数字，其中数字代表高度，其中某个格子有水的话，水可以流向周围比它低或与它相等的格子。题目问的是在这所有小格子中能否存在一个位置，这个位置的水既可流向太平洋，也可流向大西洋，有的话把坐标存下来最终返回。有一种解法是暴力枚举这里面所有的点，遇到一个点判断一下能否去太平洋和大西洋。这样方式会考虑到重复路径：

一旦矩阵规模大就会超时。我们要用正难则反策略：我们先看边界上的水它能去哪些位置。比如从1位置开始考虑，接下来就看大于等于我的位置：

所以这么多点都可经过1流向太平洋。从1开始搜索第一行就判断完了，下面考虑太平洋这一列，从2开始扩展，然后是5(因为其余位置标记过了)：

发现这些标记的都可流向太平洋。下面再判断哪些点能经过靠近大西洋的一行一列流向大西洋，那些被重复标记的点既能流向太平洋也能流向大西洋：

下面实现：