1. 概述
Flood Fill（又称种子填充）算法是一种用于确定并填充多维数组中某个连通区域的算法。它常用于图像处理中的颜色填充、游戏逻辑判断等场景。
在本文中，我们将：
- 介绍 Flood Fill 的基本定义与使用场景
- 用 BFS 和 DFS 两种方式实现 Flood Fill 算法
- 对比两种实现方式的优缺点
- 举例说明其在实际项目中的应用
2. 算法定义
Flood Fill 的核心任务是：从一个起始点出发，将与其连通且颜色相同的区域统一替换为新颜色。
算法接收两个输入参数：
start_position：起始点坐标（行、列）new_color：需要填充的新颜色
我们通常将“连通”定义为上下左右四个方向相邻的格子，且这些格子的颜色与起始点初始颜色一致。
示例说明
假设我们有一个如下所示的二维网格（每个格子表示一个像素点）：
起始点为 (2, 2)，初始颜色为蓝色，新颜色为橙色。执行 Flood Fill 后，所有与 (2, 2) 连通的蓝色区域都会被填充为橙色：
⚠️ 注意：左下角的蓝色格子未被填充，因为它与起始点不连通。
3. BFS 实现
BFS（广度优先搜索）是实现 Flood Fill 的一种常见方式。它的核心思想是使用一个队列来记录待处理的格子，逐层向外扩展。
3.1. 格子有效性判断
我们首先定义一个辅助函数 isValid()，用于判断某个格子是否可以加入队列进行处理：
boolean isValid(int row, int col, int targetColor) {
return row >= 0 && row < rows && col >= 0 && col < cols
&& grid[row][col] == targetColor
&& !visited[row][col];
}
判断条件包括：
✅ 行列在合法范围内
✅ 颜色与目标颜色一致
✅ 未被访问过
3.2. 初始实现
初始版本的 BFS 实现较为冗长，但逻辑清晰：
void floodFillBFS(int[][] grid, int sr, int sc, int newColor) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
int targetColor = grid[sr][sc];
queue.add(new int[]{sr, sc});
visited[sr][sc] = true;
grid[sr][sc] = newColor;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
// 检查四个方向
if (isValid(r+1, c, targetColor)) {
queue.add(new int[]{r+1, c});
visited[r+1][c] = true;
grid[r+1][c] = newColor;
}
if (isValid(r-1, c, targetColor)) {
queue.add(new int[]{r-1, c});
visited[r-1][c] = true;
grid[r-1][c] = newColor;
}
if (isValid(r, c+1, targetColor)) {
queue.add(new int[]{r, c+1});
visited[r][c+1] = true;
grid[r][c+1] = newColor;
}
if (isValid(r, c-1, targetColor)) {
queue.add(new int[]{r, c-1});
visited[r][c-1] = true;
grid[r][c-1] = newColor;
}
}
}
3.3. 简洁实现
我们可以使用两个方向数组简化方向遍历逻辑：
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
void floodFillBFS(int[][] grid, int sr, int sc, int newColor) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
int targetColor = grid[sr][sc];
queue.add(new int[]{sr, sc});
visited[sr][sc] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
grid[r][c] = newColor;
for (int i = 0; i < 4; i++) {
int nr = r + dx[i];
int nc = c + dy[i];
if (isValid(nr, nc, targetColor)) {
visited[nr][nc] = true;
queue.add(new int[]{nr, nc});
}
}
}
}
✅ 优点：逻辑清晰、易于理解
❌ 缺点：需要额外空间存储 visited 数组
4. DFS 实现
DFS（深度优先搜索）也是实现 Flood Fill 的一种常见方式。它通过递归的方式逐层深入，直到所有连通区域都被处理。
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
void floodFillDFS(int[][] grid, int r, int c, int newColor, int targetColor, boolean[][] visited) {
if (!isValid(r, c, targetColor, visited)) return;
grid[r][c] = newColor;
visited[r][c] = true;
for (int i = 0; i < 4; i++) {
int nr = r + dx[i];
int nc = c + dy[i];
floodFillDFS(grid, nr, nc, newColor, targetColor, visited);
}
}
boolean isValid(int r, int c, int targetColor, boolean[][] visited) {
return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length
&& grid[r][c] == targetColor && !visited[r][c];
}
✅ 优点：实现简洁、递归结构清晰
❌ 缺点：递归可能导致栈溢出，尤其在大数据量时需谨慎使用
5. 算法复杂度分析
无论是 BFS 还是 DFS，Flood Fill 的时间复杂度都是：
✅ **O(n × m)**，其中 n 是行数，m 是列数
这是因为每个格子最多被访问一次。空间复杂度也为 O(n × m)，主要来自 visited 数组和队列/栈。
6. 应用场景
Flood Fill 在实际开发中有很多应用，例如：
✅ 图像处理软件中的“油漆桶”工具
✅ 游戏中地图连通性判断（如扫雷、围棋）
✅ 判断两个点是否在同一个连通区域
✅ 地图类游戏中角色移动范围的判定
7. 小结
Flood Fill 是一种基础但非常实用的算法，适用于二维网格中连通区域的识别与操作。其核心思想简单，但实现方式多样，BFS 和 DFS 各有优劣。
在实际开发中，根据具体场景选择合适的实现方式：
- 若数据量大，建议使用 BFS 避免栈溢出风险
- 若代码结构简单，DFS 更加直观
掌握 Flood Fill，有助于你更好地处理图像处理、游戏逻辑、地图连通性等任务。