FloodFill算法详解及应用

2023-11-06 12:50| 来源: 网络整理| 查看: 265

FloodFill算法详解及应用

啥是 FloodFill 算法呢，

最直接的一个应用就是「颜色填充」，就是 Windows 绘画本中那个小油漆桶的标志，可以把一块被圈起来的区域全部染色。这种算法思想还在许多其他地方有应用。比如说扫雷游戏，有时候你点一个方格，会一下子展开一片区域，这个展开过程，就是 FloodFill 算法实现的。类似的，像消消乐这类游戏，相同方块积累到一定数量，就全部消除，也是 FloodFill 算法的功劳。

一、构建框架

以上几个例子，都可以抽象成一个二维矩阵，然后从某个点开始向四周扩展，直到无法再扩展为止。

矩阵，可以抽象为一幅「图」，这就是一个图的遍历问题，也就类似一个 N 叉树遍历的问题。几行代码就能解决，直接上框架吧：

// (x, y) 为坐标位置 void fill(int x, int y) { fill(x - 1, y); // 上 fill(x + 1, y); // 下 fill(x, y - 1); // 左 fill(x, y + 1); // 右 }

这个框架可以解决所有在二维矩阵中遍历的问题，说得高端一点，这就叫深度优先搜索（Depth First Search，简称 DFS），说得简单一点，这就叫四叉树遍历框架。坐标 (x, y) 就是 root，四个方向就是 root 的四个子节点。

看一道题：在这里插入图片描述

有了框架，直接上代码：

int[][] floodFill(int[][] image, int sr, int sc, int newColor) { int origColor = image[sr][sc]; fill(image, sr, sc, origColor, newColor); return image; } void fill(int[][] image, int x, int y, int origColor, int newColor) { // 出界：超出边界索引 if (!inArea(image, x, y)) return; // 碰壁：遇到其他颜色，超出 origColor 区域 if (image[x][y] != origColor) return; image[x][y] = newColor; fill(image, x, y + 1, origColor, newColor); fill(image, x, y - 1, origColor, newColor); fill(image, x - 1, y, origColor, newColor); fill(image, x + 1, y, origColor, newColor); } boolean inArea(int[][] image, int x, int y) { return x >= 0 && x = 0 && y // 出界：超出数组边界 if (!inArea(image, x, y)) return 0; // 已探索过的 origColor 区域 if (visited[x][y]) return 1; // 碰壁：遇到其他颜色，超出 origColor 区域 if (image[x][y] != origColor) return 0; visited[x][y] = true; int surround = fill(image, x - 1, y, origColor, newColor) + fill(image, x + 1, y, origColor, newColor) + fill(image, x, y - 1, origColor, newColor) + fill(image, x, y + 1, origColor, newColor); if (surround // ... return 1; } }

这 4 个 if 判断涵盖了 (x, y) 的所有可能情况，surround 的值由四个递归函数相加得到，而每个递归函数的返回值就这四种情况的一种。借助这个逻辑框架，你一定能理解上面那句话了。

这样就实现了仅对 origColor 区域边界坐标染色的目的，等同于完成了魔棒工具选定区域边界的功能。

这个算法有两个细节问题，一是必须借助 visited 来记录已探索的坐标，而无法使用回溯算法；二是开头几个 if 顺序不可打乱。

同理，思考扫雷游戏，应用 FloodFill 算法展开空白区域的同时，也需要计算并显示边界上雷的个数，如何实现的？

其实也是相同的思路，遇到雷就返回 true，这样 surround 变量存储的就是雷的个数。当然，扫雷的 FloodFill 算法不能只检查上下左右，还得加上四个斜向。

在这里插入图片描述

【本文地址】

公司简介

联系我们