算法讲解058 必备 洪水填充

来源：算法讲解058【必备】洪水填充　·　2026-10-23

依据：视频字幕 2000 字

一句话概括

洪水填充（Flood Fill）就是：从某个格子出发，用 DFS/BFS 把与它「上下左右连通」的同类格子全部标记掉，外层按顺序扫一遍矩阵，每触发一次填充就计一片连通块。

它解决什么问题

二维网格上统计连通块数量 / 给连通块染色 / 判断某点属于哪片区域。典型题面：'1' 表示陆地、'0' 表示水，上下左右相连的陆地算一片岛，问岛的数量。也用于：扫雷展开、图像区域染色、迷宫可达性、网格中「同色区域」的合并统计。

基础知识（前置概念，用大白话解释）

• 网格的坐标：(i, j) 表示第 i 行第 j 列，下标从 0 开始（竞赛里也常见从 1 开始，看题目输入）。
• 四连通：一个格子只和上、下、左、右四个邻居相连（不是八个方向）。八连通是变形，见「同类题」。
• DFS（深度优先搜索）：一条路走到黑，走不动再回头。这里就是「感染」：走到一个陆地，就继续往四个方向感染。
• 递归的路径信息：递归时当前在哪个格子，就是「路径信息」。洪水填充里我们不撤销这个信息——走过就标记掉，这样同一片区域不会被重复感染，也天然区分了不同的连通块。
• 连通块：能通过四连通互相到达的格子集合。一片岛 = 一个连通块。

原理（为什么这么做是对的，尽量给直觉）

想象往网格里倒水：水从某个陆地格子渗进去，凡是能连到的陆地都会被淹到，淹过的格子就变成「已访问」。因为连通关系是等价关系（自反、对称、传递），所以：

1. 从任意一个未访问的陆地出发，一次 DFS 恰好淹完它所在的整个连通块，不会漏（传递性：能连到的都能连到）。
2. 淹完的格子被标记，之后外层再扫到它们时不会重复触发，所以每个连通块恰好被计数一次。
3. 外层按「从上到下、从左到右」扫，遇到第一个未访问的陆地就说明发现了一片新岛（因为它和之前所有已淹区域都不连通）。

所以「触发 DFS 的次数」= 「连通块的数量」，这就是正确性的核心。

步骤（编号，可照着写）

1. 读入 n 行 m 列的网格（字符或整数）。
2. ans = 0。
3. 外层双重循环 i 从 0 到 n-1，j 从 0 到 m-1：

- 若 grid[i][j] 是陆地（'1'）：

- ans++

- 调用 dfs(i, j) 把整片连通块标记掉（改成 '0' 或 '2' 或访问数组置 true）。

1. dfs(i, j)：

- 越界 或 当前格子不是陆地 → 直接返回。

- 把 grid[i][j] 标记为已访问（改成非陆地字符）。

- 递归四个方向：(i-1,j) (i+1,j) (i,j-1) (i,j+1)。

1. 返回 ans。

样例（一个具体小例子，带每步变化）

网格（1=陆地，0=水）：

1 1 0 0
1 0 0 1
0 0 1 1
0 0 0 0

按行优先扫描：

| 步骤 | 扫描到 | 动作 | 网格变化（2=已淹） | ans |

|---|---|---|---|---|

| 1 | (0,0)=1 | 触发 DFS，淹 (0,0)(0,1)(1,0) | 2 2 0 0 / 2 0 0 1 / 0 0 1 1 / 0 0 0 0 | 1 |

| 2 | (0,1)=2 | 跳过 | 不变 | 1 |

| 3 | (1,3)=1 | 触发 DFS，淹 (1,3) | ... / 2 0 0 2 / 0 0 1 1 / ... | 2 |

| 4 | (2,2)=1 | 触发 DFS，淹 (2,2)(2,3) | ... / 0 0 2 2 / ... | 3 |

| 5 | 扫完 | 返回 | — | 3 |

结果 3 片岛。

代码

Python（好读，用于理解）

import sys
sys.setrecursionlimit(1 << 25)

def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    n, m = int(data[0]), int(data[1])
    grid = [list(data[2 + i * m]) for i in range(n)]  # 每行一个字符串

    def dfs(i, j):
        if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] != '1':
            return
        grid[i][j] = '2'          # 标记已访问，不撤销
        dfs(i - 1, j)
        dfs(i + 1, j)
        dfs(i, j - 1)
        dfs(i, j + 1)

    ans = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '1':
                ans += 1
                dfs(i, j)
    print(ans)

solve()

C++（竞赛风，可直接抄）

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<string> g;          // g[i][j] 是 '0'/'1'，用 string 省内存、cache 友好

void dfs(int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= m || g[i][j] != '1') return;
    g[i][j] = '2';         // 标记已访问（不撤销）
    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    g.resize(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (g[i][j] == '1') {
                ++ans;
                dfs(i, j);
            }
    cout << ans << '\n';
    return 0;
}

复杂度（时间/空间）

• 时间：每个格子最多被访问常数次（外层扫一次 + 被 DFS 淹一次），O(n·m)。最好/平均/最坏都是 O(n·m)。
• 空间：递归栈最坏 O(n·m)（整片蛇形连通块），网格本身 O(n·m)。
• 常数：DFS 版常数很小，实测比并查集快很多（视频里说「基本百分之百」）。但递归深度是隐患：n·m 到 1e6 时递归可能爆栈，见「边界与易错点」。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 「网格 + 上下左右连通 + 数连通块/染色/区域大小」。
• 「'1' 陆地 '0' 水，问岛屿数量 / 最大岛屿面积 / 被围绕的区域」。
• 「扫雷点击展开」「迷宫能否到达」「同色区域合并」。
• 数据规模 n·m 在 1e5~1e6 量级，且是静态网格（不需要动态加边）——这时洪水填充比并查集更优；若需要动态合并/离线加边，才考虑并查集。

竞赛模板（C++，可直接背）

// 网格洪水填充模板：四连通，统计连通块数量
// 输入：n 行 m 列，g[i] 为长度 m 的字符串，'1' 为陆地
int n, m;
vector<string> g;

void dfs(int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= m || g[i][j] != '1') return;
    g[i][j] = '2';
    dfs(i - 1, j); dfs(i + 1, j); dfs(i, j - 1); dfs(i, j + 1);
}

int countIslands() {
    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (g[i][j] == '1') { ++ans; dfs(i, j); }
    return ans;
}

若 n·m 可能 ≥ 1e6，把 dfs 换成显式栈的迭代版（见「竞赛补充」），避免爆栈。

边界与易错点（WA 的常见原因）

1. 越界判断顺序：必须先判 i/j 越界，再访问 g[i][j]，否则 UB/RE。C++ 里 && 短路能救你，但别写反。
2. 标记时机：进入 DFS 先标记再递归。若先递归后标记，同一格会被反复进入，最坏指数级 TLE。
3. 多测清空：多组数据时 g、ans 要重置；vector<string> 重新 resize 或 clear。
4. 递归爆栈：n·m 到 1e6 且连通块呈长蛇形时，递归深度 = 1e6，必爆。改迭代 DFS 或 BFS。
5. 字符 vs 整数：输入是字符 '1' 不是数字 1，比较别写错；若题目给的是 0/1 整数矩阵，判断条件相应改。
6. 四连通 vs 八连通：题目说「上下左右」是四连通，说「周围八个方向」才是八连通，方向数组别多写。
7. 下标从 0 还是 1：输入若 1-indexed，读入时减 1，别混。
8. 修改原网格 vs 访问数组：直接改 g 省空间，但如果后面还要用原网格（比如多问），就得用 vector<vector<char>> vis。

同类题 / 变形

• 最大岛屿面积：DFS 返回淹掉的格子数，ans = max(ans, dfs(i,j))。
• 八连通：方向数组改成 8 个 (di,dj)。
• 被围绕的区域（LeetCode 130）：先从边界上的陆地 DFS 标记「安全」，再翻转剩下的。
• 岛屿数量 II（动态加陆地）：洪水填充不适合，改用并查集。
• BFS 版：求最短步数/分层感染时用 BFS（队列），洪水填充本身不关心顺序，DFS/BFS 都行。
• 多颜色染色：把标记值从 '2' 改成连通块编号 1,2,3...，可回答「某点属于哪片」。

常见坑

• 用 list/map 存网格或邻接——常数爆炸，直接 vector<string> 或 vector<vector<char>>。
• 递归版在 1e6 网格上不测就交，RE 在栈上。
• 多测忘清 ans，第二组答案翻倍。
• 方向数组写成 8 个却按四连通题意，答案偏小。
• g[i][j] != '1' 写成 != 1（字符和整数比较），永远为真，全图不淹。

拓展（变体、实际用途、面试常问）

• 实际用途：图像编辑的「油漆桶」、扫雷展开、PS 魔棒选区、地图区域填充。
• 面试常问：岛屿数量（LeetCode 200）、最大岛屿面积（695）、被围绕的区域（130）、岛屿数量 II（305，并查集）。
• 工程变体：扫描线填充（图形学）、并查集离线合并（动态连通）。
• 性能对比：静态网格洪水填充 O(nm) 且常数极小；并查集 O(nm·α) 但常数大。视频里强调「洪水填充基本百分之百」就是指这个常数优势。

竞赛补充

以下字幕未提及，按竞赛需要补充。

1. 迭代 DFS（防爆栈）

void dfsIter(int si, int sj) {
    static int sti[1 << 22], stj[1 << 22];  // 按最大 n*m 开，或用 vector
    int top = 0;
    sti[top] = si; stj[top] = sj; ++top;
    g[si][sj] = '2';
    while (top) {
        --top;
        int i = sti[top], j = stj[top];
        static const int di[4] = {-1, 1, 0, 0};
        static const int dj[4] = {0, 0, -1, 1};
        for (int d = 0; d < 4; ++d) {
            int ni = i + di[d], nj = j + dj[d];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m || g[ni][nj] != '1') continue;
            g[ni][nj] = '2';
            sti[top] = ni; stj[top] = nj; ++top;
        }
    }
}

注意：入栈时就标记，避免同一格多次入栈导致栈溢出。

2. BFS 版（求最短步数/分层时用）

void bfs(int si, int sj) {
    queue<pair<int,int>> q;
    q.push({si, sj}); g[si][sj] = '2';
    while (!q.empty()) {
        auto [i, j] = q.front(); q.pop();
        // 四方向扩展，入队即标记
    }
}

3. 方向数组写法（比四次递归调用更整洁，也便于改八连通）

static const int di[4] = {-1, 1, 0, 0};
static const int dj[4] = {0, 0, -1, 1};

4. 多测清空模板

while (T--) {
    cin >> n >> m;
    g.assign(n, string(m, '0'));
    for (int i = 0; i < n; ++i) cin >> g[i];
    // ... 计算
}

5. 大规模输入优化：n·m 到 2e6 时，cin >> string 已足够快（sync_with_stdio(false) 后）；若仍慢，用 fread 手写读入。

自测 3 题

题 1：给定 3×3 网格

1 0 1
0 1 0
1 0 1

四连通下有几片岛？