FloodFill算法简介（用BFS、DFS算法解决）

作者：IT小白 | 2024-04-19 08:01:11

踩

FloodFill算法中文名：洪水灌溉

FloodFill通常是这样一类问题，如下图：

负数表示凹陷的土地，正数表示凸起的土地，发洪水/下雨会淹没凹陷的地方

通常会问这几种问题：

1.被淹没的区域有几块

2.被淹没的最大区域面积

3.某块背淹没区域的边长是多少

………………

本质问题：找出这块区域中性质相同的连通块

连通块可以使上下左右四个方向连同，也可以是加上斜向八个方向连通

解决方法：DFS（深度优先遍历）、BFS（广度优先遍历）

1.DFS（深度优先遍历）

从某个位置开始深度搜素，例如从右上角-1位置开始，先向下到-2，再向下到-10，再向下到-12，-12位置无法继续向下或向左右，倒退回-10，再向左到-4，再向上到-3

2.BFS（广度优先遍历）

从某个位置开始广度搜索，例如从右上角-1位置开始，-1位置上下左右搜索到-2位置，再从-2位置上下左右搜索到-3和-10位置，再分别从-3和-10位置上下左右搜索到-4和-10位置，再从-4和-10位置上下左右搜索到-12位置

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/450691