算法基础篇：（二十）一文解决 Floodfill！从原理到实战，轻松解决连通块问题

_OP_CHEN

发布于 2026-01-14 11:15:10

1290

文章被收录于专栏：C++C++

前言

在算法世界里，有一类问题总是让新手头疼 ——“找连通块”。比如 “田里有多少个水坑”“地图上有多少片森林”“如何标记被包围的区域”，这些问题本质上都属于Floodfill 问题。今天，我们就把 Floodfill 的底层逻辑、实现方法（DFS/BFS）、经典例题掰开揉碎讲清楚，让你不仅会写代码，更能理解 “为什么这么写”，从此连通块问题再也不是难题！下面就让我们正式开始吧！

一、Floodfill 是什么？—— 从 “给连通区域染色” 说起

1.1 一句话理解 Floodfill

Floodfill，直译是 “洪水填充”，就像现实中洪水蔓延一样：从某个 “起点” 出发，把所有和起点 “连通” 的区域都 “染成同一种颜色”，最终通过这种方式找到所有连通块，或者标记特定区域。

举个生活中的例子：你有一张画满格子的纸，有些格子画了 “水”（W），有些是 “旱地”（.）。现在你往一个 “水格子” 里倒墨水，墨水会扩散到所有相邻的 “水格子”（包括上下左右、斜对角），最后被墨水染过的格子就是一个 “水坑”—— 这就是 Floodfill 的核心逻辑：找到与起点连通的所有节点，并进行标记或统计。

1.2 Floodfill 的两个核心问题

所有 Floodfill 问题，本质上都围绕两个问题展开：

“连通” 的定义：两个格子是否算 “连通”？是只能上下左右（4 方向），还是包括斜对角（8 方向）？；
“操作” 的目的：找到连通块后要做什么？是统计数量（如水坑数量），还是标记区域？

1.3 Floodfill 的两种实现方式

Floodfill 的实现完全依赖搜索算法，最常用的两种方式是DFS（深度优先搜索） 和BFS（宽度优先搜索）。两者各有特点，之前的博客中已经为大家介绍过了，我们就通过一个简单对比，让大家快速回顾一下它们的差异：

实现方式	核心工具	特点	适用场景
DFS	递归 / 栈	“一条路走到黑”，代码简洁，容易实现	小规模网格，担心队列内存时
BFS	队列	“逐层扩散”，避免递归栈溢出，逻辑直观	大规模网格，需控制搜索顺序时

接下来，我们会通过具体例题，分别演示两种实现方式的用法，你可以根据实际场景选择更合适的方案。

二、Floodfill 经典例题实战 —— 从基础到进阶

光说不练假把式，接下来我们结合两道经典例题（洛谷 P1596 Lake Counting、洛谷 P1162 填涂颜色），从 “统计连通块数量” 到 “标记特定连通区域”，一步步带你掌握 Floodfill 的核心技巧。

2.1 基础款：Lake Counting（统计水坑数量）

题目链接：https://www.luogu.com.cn/problem/P1596

题目描述

农民约翰的田地被暴雨淹没，形成了多个水坑。田地用 N×M 的网格表示，每个格子是 “W”（水）或 “.”（旱地）。一个格子与周围 8 个格子（上下左右 + 斜对角）连通的 “水格子” 视为一个水坑。请统计田地中水坑的数量。

题目分析

这是 Floodfill 的入门题，核心需求是 “统计连通块数量”。解题思路非常清晰：

遍历整个网格，找到一个未被标记的 “W”（水坑起点）；
用 Floodfill（DFS 或 BFS）把这个 “W” 连通的所有 “W” 都标记为 “已访问”（避免重复统计）；
每完成一次 Floodfill，水坑数量 + 1；
遍历完所有格子，输出总数。

实现 1：DFS 版本（代码简洁，适合小规模网格）

DFS 的核心是 “递归遍历”：从起点出发，递归访问所有连通的 “W”，并标记为已访问。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;  // 题目中N、M≤100，开110足够
char g[N][N];       // 存储田地网格
bool st[N][N];      // 标记是否已访问
int n, m;

// 8个方向的方向数组（上下左右+斜对角）
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

// DFS：从(x,y)出发，标记所有连通的W
void dfs(int x, int y) {
    st[x][y] = true;  // 标记当前格子已访问
    // 遍历8个方向
    for (int k = 0; k < 8; k++) {
        int nx = x + dx[k];  // 新格子的x坐标
        int ny = y + dy[k];  // 新格子的y坐标
        // 检查边界：nx在1~n，ny在1~m（注意：网格从1开始更直观）
        // 检查是否未访问且是水（W）
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !st[nx][ny] && g[nx][ny] == 'W') {
            dfs(nx, ny);  // 递归访问新格子
        }
    }
}

int main() {
    cin >> n >> m;
    // 读入网格（注意：这里从1行1列开始存储，避免边界判断麻烦）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }

    int cnt = 0;  // 统计水坑数量
    // 遍历整个网格
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 找到未访问的W，触发Floodfill
            if (!st[i][j] && g[i][j] == 'W') {
                cnt++;
                dfs(i, j);
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

实现 2：BFS 版本（避免栈溢出，适合大规模网格）

BFS 的核心是 “队列遍历”：从起点出发，把连通的 “W” 依次加入队列，逐层标记，逻辑更接近 “洪水扩散” 的直观过程。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;  // 存储坐标（x,y）
const int N = 110;
char g[N][N];
bool st[N][N];
int n, m;

// 8方向方向数组（和DFS一致）
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

// BFS：从(x,y)出发，标记所有连通的W
void bfs(int x, int y) {
    queue<PII> q;          // 队列存储待标记的格子
    q.push({x, y});        // 起点入队
    st[x][y] = true;       // 标记已访问

    while (!q.empty()) {   // 队列不为空，继续扩散
        auto t = q.front();// 取出队头格子
        q.pop();
        int x = t.first, y = t.second;

        // 遍历8个方向
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 边界+未访问+是水
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !st[nx][ny] && g[nx][ny] == 'W') {
                st[nx][ny] = true;  // 标记已访问
                q.push({nx, ny});   // 新格子入队，等待后续扩散
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!st[i][j] && g[i][j] == 'W') {
                cnt++;
                bfs(i, j);
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

关键细节与避坑指南

方向数组的选择：本题是 8 方向连通（水坑会向斜对角扩散），所以方向数组要包含 8 个方向；如果是 4 方向连通（如上下左右），只需保留前 4 个方向即可；
网格的坐标起点：建议从 1 开始存储网格（而非 0），这样边界判断（nx≥1 && nx≤n）更直观，避免出现 “nx=-1” 这类容易忽略的错误；
标记数组的作用：st[N][N]必须在访问前标记，否则会导致同一个格子被重复加入队列 / 递归，引发超时或栈溢出；
DFS vs BFS 的选择：当网格规模较小时（如 N、M≤100），DFS 代码更简洁；当网格规模大时（如 N、M≤1e3），DFS 可能触发递归栈溢出（C++ 默认递归深度约为 1e4），此时 BFS 更安全。

2.2 进阶款：填涂颜色（标记特定连通区域）

题目链接：https://www.luogu.com.cn/problem/P1162

题目描述

在 n×n 的 01 方阵中，有一个由 1 构成的闭合圈。要求把闭合圈内的所有 0 都填成 2。规则：如果从某个 0 出发，仅通过上下左右 4 个方向移动且只经过 0，无法到达方阵边界，那么这个 0 就在闭合圈内。

题目分析

这道题是 Floodfill 的 “反向思维” 经典案例。直接找 “闭合圈内的 0” 很困难（因为你不知道哪个 0 被包围），但反过来想：能到达边界的 0 一定不在圈内，不能到达边界的 0 一定在圈内。

所以解题思路可以 “正难则反”：

用 Floodfill 标记所有 “能到达边界的 0”（这些 0 是 “外圈 0”，不需要填 2）；
遍历整个网格：
- 如果是 1：保持不变；
- 如果是 0 且被标记：保持不变（外圈 0）；
- 如果是 0 且未被标记：填成 2（圈内 0）。

技巧：给网格 “加一层外套”

为了简化边界判断，我们可以给原始网格 “外围加一层 0”（比如原始 n×n 网格，变成 (n+2)×(n+2) 网格），这样只需从 (0,0) 这个 “外套格子” 出发，一次 Floodfill 就能标记所有能到达边界的 0，无需单独遍历原始网格的四条边。

完整代码（BFS 实现，更直观）

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
const int N = 35;  // 题目中n≤30，加2层外套后35足够
int g[N][N];        // 存储01方阵（加外套后）
bool st[N][N];      // 标记“能到达边界的0”
int n;

// 4方向方向数组（本题是上下左右连通，无斜对角）
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// BFS：从(x,y)出发，标记所有能到达边界的0
void bfs(int x, int y) {
    queue<PII> q;
    q.push({x, y});
    st[x][y] = true;  // 外套格子本身是0，标记为已访问

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;

        // 遍历4个方向
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 边界判断：nx在0~n+1，ny在0~n+1（外套的范围）
            // 检查：未访问 + 是0（只有0能扩散）
            if (nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= n + 1 && !st[nx][ny] && g[nx][ny] == 0) {
                st[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    cin >> n;
    // 初始化加外套的网格（0~n+1行，0~n+1列）
    memset(g, 0, sizeof g);  // 外套部分默认是0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];  // 读入原始网格（1~n行，1~n列）
        }
    }

    // 从外套的(0,0)出发，标记所有能到达边界的0
    bfs(0, 0);

    // 输出结果：处理原始网格（1~n行，1~n列）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] == 1) {
                // 1保持不变
                cout << 1 << " ";
            } else if (st[i][j]) {
                // 0且被标记：外圈0，保持不变
                cout << 0 << " ";
            } else {
                // 0且未被标记：圈内0，填2
                cout << 2 << " ";
            }
        }
        cout << endl;  // 每行结束换行
    }

    return 0;
}

代码解释与关键技巧

网格外套的作用：原始网格的边界 0 需要单独遍历，而加外套后，(0,0) 是外套的起点，一次 BFS 就能覆盖所有能到达边界的 0，代码更简洁；
方向数组的选择：本题中 0 只能通过上下左右移动到达边界，所以用 4 方向数组，不能加斜对角（否则会错误标记圈内 0）；
标记数组的含义：st[N][N]标记的是 “能到达边界的 0”，而非 “已访问的格子”—— 这是 Floodfill 的灵活应用，标记的是 “特定属性的区域”，而非单纯的访问状态；
结果处理逻辑：输出时只处理原始网格（1~n 行，1~n 列），外套部分不输出，避免影响结果格式。

测试用例演示

以题目中的示例输入为例：

输入（n=6）：

加外套后，BFS 从 (0,0) 出发，标记所有能到达边界的 0（如第一行的 0、第二行的 0 等）；

输出时，未被标记的 0（圈内 0）被填成 2，最终结果如下：

0 0 0 0 0 0 
0 0 1 1 1 1 
0 1 1 2 2 1 
1 1 2 2 2 1 
1 2 2 2 2 1 
1 1 1 1 1 1

三、Floodfill 的通用解题框架

通过上面两道例题，我们可以总结出 Floodfill 问题的通用解题框架，无论遇到什么连通块问题，都可以按这个步骤思考：

步骤 1：明确 “连通定义” 和 “目标”

连通定义：4 方向？8 方向？是否允许穿过障碍物（如 1、* 等）？
目标：统计连通块数量？标记特定区域？修改区域值？

步骤 2：选择 Floodfill 实现方式（DFS/BFS）

小规模网格 / 代码简洁优先：选 DFS；
大规模网格 / 避免栈溢出：选 BFS；
需逐层扩散 / 直观展示：选 BFS。

步骤 3：设计 “标记策略”

统计数量：标记 “已访问”，避免重复统计；
标记区域：标记 “目标属性”（如 “能到达边界”“在圈内” 等）；
空间优化：如果网格本身可以修改（如把 W 改成.），可以用网格自身作为标记，省去st[N][N]数组（但需注意题目是否允许修改输入）。

步骤 4：处理边界与特殊情况

边界判断：建议网格从 1 开始存储，或加外套，避免边界错误；
特殊输入：如全是障碍物、全是目标区域等，需确保 Floodfill 能正常处理；
多组数据：每次处理前需重置网格和标记数组，避免数据污染。

四、Floodfill 的避坑指南

方向数组写错：比如把 8 方向写成 4 方向，导致连通块漏统计；或方向数组元素错误（如 dx 写成 {0,0,1,1}），导致扩散方向错误；
边界判断失误：比如网格从 0 开始存储，却用 nx>=1 作为边界，导致漏判第一行；或 nx<=n 写成 nx<n，漏判最后一行；
标记数组未重置：多组数据时，st[N][N]或dist[N][N]未用 memset 重置，导致上一组数据的标记影响当前组；
递归栈溢出：DFS 处理大规模网格（如 n=1e3）时，递归深度超过 C++ 默认栈大小（约 1e4），导致程序崩溃；
混淆连通定义：比如填涂颜色问题用 8 方向扩散，导致错误标记圈内 0，结果错误。

总结

Floodfill 是算法入门的重要知识点，也是面试中的高频考点。掌握它，你不仅能解决 “连通块” 类问题，更能培养 “扩散思维” 和 “反向思维”，为后续学习更复杂的搜索算法（如 BFS 最短路径、DFS 剪枝）打下基础。最后，留一个小思考题：如果网格中有两种 “水”（W1 和 W2），如何统计同时与 W1 和 W2 连通的旱地（.）数量？欢迎在评论区交流你的思路～

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-28，如有侵权请联系 cloudcommunity@tencent.com 删除

数组