一、什么是Flood Fill？

1.1 基本概念

Flood Fill，中文通常叫 洪水填充算法，它是一类基于搜索的经典模型。

它的核心思想是：

从某个起点出发，沿着合法方向不断扩展，把与起点连通的所有合法位置都访问一遍。

在算法竞赛中，Flood Fill 经常用于处理；

二维网格中的连通块
岛屿数量
区域染色
迷宫可达性
棋盘区域扩展
图像填色
地图区域统计

它本质上是 DFS 或 BFS 在二维网格上的应用。

二、Flood Fill 的经典问题模型

2.1 二维网格模型

通常题目会给你一个二维矩阵，例如：

其中：

1 表示陆地
0 表示水域

如果题目让你求“岛屿数量”，那么问题就可以转化为：

有多少个由 1 组成的连通块？

这里的每一个岛屿，就是一个连通块。

三、什么是连通？

3.1 四方向连通

算法竞赛中最常见的是 上下左右四个方向连通：

    上
左  当前  右
    下

方向数组可以写成：

int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

表示：

(-1, 0)  上
(0, 1)   右
(1, 0)   下
(0, -1)  左

3.2 八方向连通

有些题目中，斜对角也算连通，这时就是 八方向连通：

左上  上  右上
左   当前  右
左下  下  右下

方向数组：

int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

四、Flood Fill 的核心思想

Flood Fill 的标准流程是：

遍历整个网格。
如果发现一个没有访问过的合法格子，就说明找到了一个新的连通块。
从这个格子开始进行 DFS 或 BFS。
把与它连通的所有合法格子都标记为已访问。
继续遍历网格，寻找下一个新的连通块。

以“岛屿数量”为例：

从左上角的 1 开始搜索，可以找到左上角这一片岛屿：

之后继续扫描，又会找到右下角那一片岛屿：

A A 0 0
A 0 0 B
0 0 B B
0 0 0 B

所以答案是 2。

五、Flood Fill 的 DFS 写法

5.1 DFS 思路

DFS，也就是深度优先搜索。

在 Flood Fill 中，DFS 的逻辑是：

进入当前格子后，继续尝试访问它的上下左右邻居，直到走不动为止。

5.2 DFS 模板

static int n, m;
static char[][] grid;
static boolean[][] visited;

static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};

static void dfs(int x, int y) {
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
            continue;
        }

        if (visited[nx][ny]) {
            continue;
        }

        if (grid[nx][ny] != '1') {
            continue;
        }

        dfs(nx, ny);
    }
}

主函数中的遍历逻辑：

int count = 0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (grid[i][j] == '1' && !visited[i][j]) {
            count++;
            dfs(i, j);
        }
    }
}

这里的 count++ 表示发现了一个新的连通块。

六、Flood Fill 的 BFS 写法

6.1 BFS 思路

BFS，也就是广度优先搜索。

DFS 是“一条路走到底”，BFS 是“一层一层扩展”。

在 Flood Fill 中，BFS 的逻辑是：

把起点加入队列。
不断从队列中取出当前格子。
尝试访问它的上下左右邻居。
合法且未访问的邻居加入队列。
队列为空时，当前连通块搜索结束

6.2 BFS 模板

static void bfs(int x, int y) {
    Queue<int[]> queue = new LinkedList<>();

    queue.offer(new int[]{x, y});
    visited[x][y] = true;

    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int cx = cur[0];
        int cy = cur[1];

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }

            if (visited[nx][ny]) {
                continue;
            }

            if (grid[nx][ny] != '1') {
                continue;
            }

            visited[nx][ny] = true;
            queue.offer(new int[]{nx, ny});
        }
    }
}

6.3 DFS 和 BFS 的区别

对比项	DFS	BFS
搜索方式	一条路走到底	一层一层扩展
常用结构	递归 / 栈	队列
代码简洁度	通常更简洁	稍微复杂
栈溢出风险	有，递归太深可能爆栈	一般没有递归爆栈问题
适合场景	连通块统计、区域遍历	最短路、层数扩展、连通块统计

在 Flood Fill 中，如果只是统计连通块，DFS 和 BFS 都可以。

如果网格很大，递归 DFS 可能会爆栈，这时建议使用 BFS 或手写栈模拟 DFS。

七、Flood Fill 的常见题型

7.1 统计连通块数量

典型问题：

给定一个二维矩阵，求有多少个由 1 组成的连通块。

这就是最基础的 Flood Fill。

核心代码：

if (grid[i][j] == '1' && !visited[i][j]) {
    count++;
    dfs(i, j);
}

每次遇到一个未访问过的 1，说明遇到了一个新的连通块。

7.2 求最大连通块面积

题目可能会问：

最大岛屿面积是多少？

这时 DFS 不仅要访问连通块，还要返回当前连通块的大小。

static int dfsArea(int x, int y) {
    visited[x][y] = true;

    int area = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
            continue;
        }

        if (visited[nx][ny]) {
            continue;
        }

        if (grid[nx][ny] != '1') {
            continue;
        }

        area += dfsArea(nx, ny);
    }

    return area;
}

主逻辑：

int maxArea = 0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (grid[i][j] == '1' && !visited[i][j]) {
            int area = dfsArea(i, j);
            maxArea = Math.max(maxArea, area);
        }
    }
}

7.3 区域染色

题目可能会问：

从某个点开始，把与它相连的同色区域全部染成另一种颜色。

这就是经典的图像填色问题。

例如：

1 1 1
1 1 0
1 0 1

从 (1, 1) 开始，把连通的 1 改成 2：

2 2 2
2 2 0
2 0 1

注意右下角的 1 没有被染色，因为它和起点不连通。

代码：

static void floodFill(int x, int y, int oldColor, int newColor) {
    if (x < 0 || x >= n || y < 0 || y >= m) {
        return;
    }

    if (grid[x][y] != oldColor) {
        return;
    }

    grid[x][y] = newColor;

    for (int i = 0; i < 4; i++) {
        floodFill(x + dx[i], y + dy[i], oldColor, newColor);
    }
}

一个很重要的细节：

if (oldColor == newColor) {
    return;
}

如果原颜色和新颜色相同，不提前返回，可能会导致重复递归。

7.4 判断是否能从起点走到终点

迷宫类问题经常这样问：

给定一个地图，. 表示空地，# 表示墙，判断能否从 S 走到 T。

这时 Flood Fill 用来判断可达性。

核心逻辑：

static boolean dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) {
        return false;
    }

    if (grid[x][y] == '#') {
        return false;
    }

    if (visited[x][y]) {
        return false;
    }

    if (grid[x][y] == 'T') {
        return true;
    }

    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        if (dfs(x + dx[i], y + dy[i])) {
            return true;
        }
    }

    return false;
}

7.5 被包围区域问题

例如题目给出：

X X X X
X O O X
X X O X
X O X X

要求把被 X 包围的 O 改成 X。

结果：

X X X X
X X X X
X X X X
X O X X

这类题目的关键思路是：

不要直接找被包围的区域，而是先从边界出发，找到所有“不可能被包围”的 O。

步骤：

从边界上的 O 开始 Flood Fill。
把所有能从边界连通到的 O 标记为安全区域。
遍历整个矩阵：
- 没有被标记的 O 改成 X
- 被标记的安全区域改回 O

这种思路很常见，属于 Flood Fill 的进阶应用。

八、Flood Fill 的复杂度分析

假设网格大小为 n * m。

每个格子最多被访问一次。

所以时间复杂度是： $O(n*m)$

空间复杂度主要来自 visited 数组和搜索结构。 $O(n*m)$

九、Flood Fill 的常见易错点

9.1 忘记判断边界

访问数组之前一定要先判断：

if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
    continue;
}

否则会数组越界。

9.2 忘记标记 visited

如果不标记访问状态，搜索可能会在两个相邻格子之间反复递归，导致死循环。

9.3 visited 标记时机错误

BFS 中，建议在加入队列时就标记：

visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});

不要等到出队时才标记，否则同一个点可能会被重复加入队列。

9.4 递归 DFS 可能爆栈

如果地图特别大，比如：1000 * 1000 并且全是陆地，那么递归深度可能非常大。

Java 中递归层数过深容易出现：StackOverflowError，这时可以改用 BFS 或手写栈。

十、Flood Fill 总结

Flood Fill 是算法竞赛中非常基础但非常重要的搜索模型。

它的本质是：

从一个起点出发，通过 DFS 或 BFS，把所有与起点连通的合法位置全部访问一遍。

它常用于解决：

连通块数量
最大连通块面积
图像染色
迷宫可达性
岛屿问题
被包围区域
棋盘区域扩展

写 Flood Fill 时，重点关注四件事：

搜索起点是什么？
哪些格子是合法的？
使用四方向还是八方向？
如何避免重复访问？

只要把这四点想清楚，大多数 Flood Fill 问题都可以顺利解决。

10.1 题目推荐

OJ平台	题号
洛谷	P1451
HDUOJ	1312
POJ	2836

Flood Fill 看起来只是简单的 DFS 或 BFS，但它在算法竞赛中的出现频率非常高。很多看似复杂的地图、棋盘、岛屿、迷宫问题，本质上都可以抽象成“从某个点出发，寻找一个连通区域”的问题。

掌握 Flood Fill 后，再学习图搜索、最短路、多源 BFS、拓扑排序等内容会更加自然。

Kyrie

从岛屿数量开始理解 Flood Fill：搜索算法中的经典连通块模型