🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
⭐FloodFill⭐
🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
前言
Flood Fill算法，也被称为种子填充算法，是一种在计算机图形学和图像处理中广泛使用的算法。它的主要用途是从一个给定的起始点（称为“种子”）开始，填充与该点颜色相同且相连的区域。这个过程类似于洪水从一个点开始蔓延到周围的连通区域，直到遇到边界或不同的颜色。
1. 工作原理
- 选择起始点：用户选择一个起始点（通常是图像中的一个像素），作为填充操作的起点。
- 检查当前点：算法会检查当前点的颜色是否符合填充条件（比如，是否是目标颜色）。
- 改变颜色：如果符合条件，则将当前点的颜色更改为新的指定颜色。
- 递归或迭代扩展：接着，算法会检查当前点周围相邻的点，并重复步骤2和3。这个过程可以递归地进行，也可以使用队列或栈来迭代实现。
- 停止条件：当所有符合条件的相邻点都被处理过后，算法就会停止。
2. 实现方式
Flood Fill算法通常有两种实现方法：
- 深度优先搜索 (DFS): 使用递归或显式堆栈来进行填充。每次找到一个符合条件的点时，就立即深入探索其邻居。
- 广度优先搜索 (BFS): 使用队列来实现。先处理起始点，然后依次处理它所有的直接邻居，再处理这些邻居的邻居，以此类推。
3. 应用场景
图像编辑软件：如Photoshop等软件中的油漆桶工具。
游戏开发：例如扫雷游戏中点击空白处展开相邻格子的功能。
地图着色：在地图上标记特定区域。
数据可视化：热力图、地形渲染等。
计算机视觉：图像分割、边缘检测等。
4. 示例代码模板
下面是一个简单的Flood Fill算法示例，使用了深度优先搜索(DFS)来实现：
public class FloodFill {private static final int[] dx = {0, 0, -1, 1};private static final int[] dy = {-1, 1, 0, 0};public void floodFill(char[][] grid, int x, int y, char oldColor, char newColor) {// 检查坐标是否越界if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return;// 如果不是旧颜色或者已经是新颜色，不需要填充if (grid[x][y] != oldColor || grid[x][y] == newColor) return;// 更改当前点的颜色grid[x][y] = newColor;// 对当前点的四个方向递归调用floodFillfor (int i = 0; i < 4; i++) {floodFill(grid, x + dx[i], y + dy[i], oldColor, newColor);}}
}这段代码定义了一个floodFill方法，接受一个二维字符数组grid表示图像，以及两个坐标x和y作为起始点，还有需要替换的旧颜色oldColor和新颜色newColor。通过递归的方式，它会把从起始点开始的所有连续的oldColor都替换成newColor。
5: 经典例题 : 岛屿数量（medium）
题⽬链接：200. 岛屿数量 - 力扣（LeetCode）
算法思路
目的：找出二维网格中不相连的所有'1'（代表陆地）的集合个数。
步骤：
- 遍历网格中的每一个格子。
- 如果发现了一个未被访问的陆地块（值为'1'且未被标记），则增加岛屿计数。
- 对该陆地块进行深度优先搜索，将其以及与之相连的所有陆地块都标记为已访问。
- 继续遍历直到检查完所有的格子。
代码实现
class Solution {// 方向数组，用于探索四个可能的方向int[] dx = new int[]{0, 0, -1, 1};int[] dy = new int[]{1, -1, 0, 0};public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) return 0;int m = grid.length; // 行数int n = grid[0].length; // 列数boolean[][] vis = new boolean[m][n]; // 访问标记数组int count = 0; // 岛屿计数for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 发现新的陆地并且没有被访问过if (grid[i][j] == '1' && !vis[i][j]) {count++; // 增加岛屿计数dfs(grid, vis, i, j); // 使用DFS淹没这个岛屿}}}return count;}private void dfs(char[][] grid, boolean[][] vis, int x, int y) {// 标记当前陆地为已访问vis[x][y] = true;// 探索四周的四个方向for (int k = 0; k < 4; k++) {int newX = x + dx[k];int newY = y + dy[k];// 检查新坐标是否越界，是否是陆地，是否已经访问过if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length&& grid[newX][newY] == '1' && !vis[newX][newY]) {// 递归调用dfs继续淹没dfs(grid, vis, newX, newY);}}}
}class Solution {// 方向数组，用于探索四个可能的方向int[] dx = new int[]{0, 0, -1, 1};int[] dy = new int[]{1, -1, 0, 0};public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) return 0;int m = grid.length; // 行数int n = grid[0].length; // 列数boolean[][] vis = new boolean[m][n]; // 访问标记数组int count = 0; // 岛屿计数for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 发现新的陆地并且没有被访问过if (grid[i][j] == '1' && !vis[i][j]) {count++; // 增加岛屿计数dfs(grid, vis, i, j); // 使用DFS淹没这个岛屿}}}return count;}private void dfs(char[][] grid, boolean[][] vis, int x, int y) {// 标记当前陆地为已访问vis[x][y] = true;// 探索四周的四个方向for (int k = 0; k < 4; k++) {int newX = x + dx[k];int newY = y + dy[k];// 检查新坐标是否越界，是否是陆地，是否已经访问过if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length&& grid[newX][newY] == '1' && !vis[newX][newY]) {// 递归调用dfs继续淹没dfs(grid, vis, newX, newY);}}}
}总结
FloodFill 思想正如其名，像洪水一样浇灌低谷，一般通过 BFS 或者 DFS 实现，如果你帮我主页中的回溯算法题都刷完了，写这个算法是很轻松的，就像简化版的回溯问题一样，甚至不需要剪枝。以上就是今天的内容，后续会更新更多，感谢阅览！！！
