第 13 章 DFS 深度优先搜索：网格连通块

这一章和第 14 章用同一张地图

第 14 章讲 BFS 时会用完全相同的 8×8 网格。学完两章之后，把两个动画摆在一起看一遍 ——「深度优先」和「广度优先」的差别，用看的比用背的清楚一百倍。

1一句话问题

给一张 n × m 的网格，1 是陆地，0 是水。上下左右相邻的陆地算同一块。问一共有几块陆地。

输入

输出

第一行是行数和列数，之后是地图。1 是陆地、0 是水，四连通的陆地算一块。这张图上是 3 块。

2先用纸笔手算一遍

拿铅笔在上面那张 4×5 的图上圈一圈：左上角 2×2 的四个格子是一块，中间孤零零的 (2,2) 是一块，右下角 (3,3) (3,4) 是一块。共 3 块。

现在请注意你自己刚才是怎么圈的：你多半是把笔尖点在一个格子上，然后顺着相连的格子一路滑过去，直到滑不动了才回头。

这就是 DFS。你的手已经会了，只是还没翻译成代码。

3暴力：反复扫描整张图

假设你还不会 DFS。最自然的想法是：

找一个还没标记的陆地格，标记上，作为这一块的起点。然后一轮一轮往外扩张 —— 每一轮扫描整张图，把所有「紧挨着已标记格子」的陆地也标记上。某一轮下来一个新的都没有了，说明这块扩张完了，块数 +1，去找下一个起点。

brute.cpp暴力

// 数连通块 —— 暴力：反复扫描整张图
//
// 输入：第一行 n m，接下来 n 行每行 m 个字符，'1' 是陆地，'0' 是水
// 输出：四连通的陆地连通块个数
//
// 这是「不会 DFS 的人」最自然会想到的办法：
//   找一个还没标记的陆地格，把它标记上，作为一块的起点；
//   然后一轮一轮地扩张 —— 每一轮扫描整张图，
//   把所有「紧挨着上一轮已标记格子」的陆地也标记上（同一轮之内互不影响）；
//   某一轮下来没有任何新增了，说明这一块扩张完了，块数 +1，去找下一个起点。
//
// 它是对的，思路也朴素得让人放心。问题是它太笨了：
// 每往外扩张一层，就要把整张 n×m 的图重新扫一遍。
// 如果这一块长得像一条蜿蜒的长蛇（长度 L），就要扫 L 轮，
// 总代价是 O(Lnm)，最坏能到 O((nm)²)。
//
// 140×140 的蛇形图上，它要跑接近十亿次操作 —— 你能亲眼看到它卡在那里。

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

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    vector<vector<char>> vis(n, vector<char>(m, 0));
    int blocks = 0;

    for (int si = 0; si < n; si++) {
        for (int sj = 0; sj < m; sj++) {
            if (g[si][sj] != '1' || vis[si][sj]) continue;

            // 找到一块新的，先把起点标记上
            blocks++;
            vis[si][sj] = 1;

            // 一轮一轮往外扩张，直到这一块不再长大
            bool grew = true;
            while (grew) {
                grew = false;
                // 拿上一轮结束时的状态做判断，保证这一轮里大家「同时」向外走一步
                vector<vector<char>> old = vis;
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if (g[i][j] != '1' || old[i][j]) continue;
                        for (int d = 0; d < 4; d++) {
                            int x = i + dx[d], y = j + dy[d];
                            if (x < 0 || x >= n || y < 0 || y >= m) continue;
                            if (old[x][y]) {          // 挨着一个上一轮就已标记的格子
                                vis[i][j] = 1;
                                grew = true;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    cout << blocks << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

这个思路完全正确，而且朴素得让人放心。问题在第 5 步。

4实测：它到底有多慢

小图上看不出问题。换一张 200×200 的「蛇形长廊」：整张图只有一块陆地，但这一块被拉成了一条又长又绕的通道（长度约两万格）。点右上角的 「开始对比 ▶」。

同题对比：反复扫描 vs DFS

网格边长

生成一条蛇形长廊：整张图只有 1 个连通块，但通道极长。先用 200 跑一次，再改成 240 试试。

反复扫描

DFS

在我的机器上：暴力约 1.0 秒，DFS 约 0.003 秒 —— 差了三百多倍。把边长改成 240，暴力会涨到 2 秒多，而 DFS 纹丝不动。

5慢在哪

慢在这一句：每往外扩张一层，就要把整张 n×m 的图重新扫一遍。

蛇形长廊的通道长约 L = 20000 格，所以要扫 20000 轮，每轮 40000 个格子 —— 八亿次操作。而整张图一共才 40000 个格子。

问题的根子在于暴力的姿态是被动的：它站在原地反复扫，等着陆地自己「长」过来。可我们手算的时候明明不是这样 —— 我们是拿着笔主动滑过去的。

6★ 关键的一步

★ 关键的一步

既然我站在一个陆地格上，我完全可以自己走过去，何必反复扫全图等它长过来？

走到一个格子 → 染上色 → 立刻从这个格子继续往四个方向走 → 走过的不再走。

「走到一个新格子，然后从这个新格子继续做同样的事」—— 这句话翻译成代码，就是函数调用自己。

于是每个格子只被访问一次：O(Lnm) → O(nm)。

dfs(i, j) 的职责（第 1 章的三要素，一个都不能少）：

要素	内容
职责	我站在格子 (i,j) 上，负责把所有和它连通的、还没染色的陆地全部染上色
边界	不用写显式的 `return` —— 当四个方向都「出界 / 是水 / 已染色」时，for 循环自然结束
递推	对四个方向的每个合法邻居 `(x,y)`，调用 `dfs(x, y)`

⚠ 边界在哪？很多人在这里犯迷糊

第 1 章的递归有一行显眼的 if (n == 0) return 0;，DFS 里却好像找不到出口。

出口藏在那三个 continue 里：出界、是水、已经染过色。这三个条件挡住了所有分支，for 循环走完，函数自然返回 —— 这就是边界。

其中「已经染过色」是最关键的那个。删掉它，两个相邻格子会互相无限调用，瞬间栈溢出。第 10 步的对拍会让你亲眼看到这个后果。

7DFS 写法

fast.cpp正解

// 数连通块 —— DFS 染色
//
// 和 brute.cpp 解同一道题，答案必须一样，但快得多。
//
// 关键的那一步想法：
//   暴力之所以慢，是因为它「站在原地反复扫全图，等着块自己长过来」。
//   可是从一个陆地格出发，我完全可以「自己走过去」——
//   走到一个格子，就立刻从它继续往四个方向走，走过的就染上色不再走。
//   这样每个格子只会被访问一次，一趟就能把整块走完。
//
//   O(Lnm)  →  O(nm)
//
// 而「走到一个格子，就从它继续往下走」这句话，翻译成代码就是函数调用自己 —— 递归。
// DFS 不是什么新东西，它就是第 1 章那个递归，只不过递归的对象从「数字」变成了「格子」。
//
// dfs(i, j) 的含义：我现在站在格子 (i,j) 上，负责把和它连通的、还没染色的陆地全部染上色。

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

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

int n, m;
vector<string> g;
vector<vector<char>> vis;

void dfs(int i, int j) {
    vis[i][j] = 1;                       // 先给脚下这格染色
    for (int d = 0; d < 4; d++) {        // 再看四个方向
        int x = i + dx[d], y = j + dy[d];
        if (x < 0 || x >= n || y < 0 || y >= m) continue;   // 出界
        if (g[x][y] != '1') continue;                        // 是水
        if (vis[x][y]) continue;                             // 已经染过了
        dfs(x, y);                                           // 走过去，重复同样的事
    }
}

int main() {
    if (!(cin >> n >> m)) return 0;
    g.resize(n);
    for (int i = 0; i < n; i++) cin >> g[i];
    vis.assign(n, vector<char>(m, 0));

    int blocks = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '1' && !vis[i][j]) {
                blocks++;      // 每发起一次 dfs，就意味着发现了一块新的
                dfs(i, j);
            }
        }
    }

    cout << blocks << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

注意主函数里的这个模式，它是所有连通块问题的通用骨架：

for (每个格子)
    if (是陆地 && 还没染色) {
        blocks++;        // 每发起一次 dfs，就意味着发现了一块新的
        dfs(i, j);       // 这一次调用会把整块都染完
    }

「发起了几次 DFS」和「有几个连通块」是同一个数 —— 想明白这一点，这道题就通了。

8把 DFS 的脚印打印出来

trace.cpp过程演示

缩进 = 递归深度 = 你离出发点有多远。注意「退回上一层」之后发生了什么。

// 数连通块 —— 带打印的 DFS，用来「看见」它是怎么走的
//
// 用小图跑（8×8 以内），观察两件事：
//   1. 它是「一条道走到黑」的：先顺着一个方向猛扎到底，走不动了才退回来换方向。
//      这就是「深度优先」四个字的字面意思。
//   2. 退回来的那一步（<- 退回）不是白走的 —— 退回上一层后，
//      上一层的 for 循环会接着试下一个方向。
//
// 缩进 = 递归深度 = 你现在离出发点有多远。

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

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const char* dname[4] = {"上", "下", "左", "右"};

int n, m;
vector<string> g;
vector<vector<char>> vis;
int order = 0;

void indent(int d) { for (int i = 0; i < d; i++) cout << "|  "; }

void dfs(int i, int j, int depth) {
    vis[i][j] = 1;
    order++;
    indent(depth);
    cout << "第 " << order << " 个走到 (" << i << "," << j << ")  深度=" << depth << "\n";

    for (int d = 0; d < 4; d++) {
        int x = i + dx[d], y = j + dy[d];
        if (x < 0 || x >= n || y < 0 || y >= m) continue;
        if (g[x][y] != '1') continue;
        if (vis[x][y]) continue;
        indent(depth);
        cout << "   往" << dname[d] << "走 -> (" << x << "," << y << ")\n";
        dfs(x, y, depth + 1);
    }

    indent(depth);
    cout << "<- (" << i << "," << j << ") 四个方向都试完了，退回上一层\n";
}

int main() {
    if (!(cin >> n >> m)) return 0;
    g.resize(n);
    for (int i = 0; i < n; i++) cin >> g[i];
    vis.assign(n, vector<char>(m, 0));

    int blocks = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '1' && !vis[i][j]) {
                blocks++;
                cout << "\n===== 发现第 " << blocks << " 块，从 (" << i << "," << j << ") 出发 =====\n";
                order = 0;
                dfs(i, j, 0);
            }
        }
    }

    cout << "\n连通块总数 = " << blocks << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

读输出的时候找这两处：

缩进一路变深 —— 它顺着一个方向猛扎，走不动了才停。
出现 <- ... 退回上一层 之后，上一层紧接着又往别的方向走了 —— 退回不是失败，是让上一层的 for 循环接着试下一个方向。

9单步看 DFS 怎么走

DFS 染色：一条道走到黑共 142 步

第 1 / 142 步

灰色方块是墙 / 水，不能走。

格子里的数字 = 第几个被走到。白框 = 还在递归栈里（还没走完的祖先），黑框 = 当前所在。

换一张地图试试（1 = 能走，0 = 墙）

已找到连通块

递归栈（深度 0）

（空）

从头扫描时发现 (0,0) 是块没染色的陆地 —— 这是第 1 块，从它发起一次 DFS。

这张 8×8 地图和第 14 章的完全一样。播放时盯住：

格子里的数字是访问顺序。看它是怎么「拉成一条线」的 —— 不是一圈圈铺开。
右边那根递归栈，和第 1 章调用栈动画里的柱子是同一个东西，只是装的从数字变成了格子。
栈突然变矮的那些时刻，就是「一条道走到黑之后往回退」。
三块陆地用三种颜色 —— 每种颜色对应主函数里的一次 dfs 调用。

10★ 对拍验证

★ 正确的用法

把「DFS 版」那一栏换成你自己默写的，再点开始。

对拍器

轮数

生成器造 8×8 以内、陆地水各占一半的随机小图 —— 这种数据最容易造出奇形怪状的连通块，也就最容易把错误代码逼出原形。

// 数连通块 —— DFS 染色
//
// 和 brute.cpp 解同一道题，答案必须一样，但快得多。
//
// 关键的那一步想法：
//   暴力之所以慢，是因为它「站在原地反复扫全图，等着块自己长过来」。
//   可是从一个陆地格出发，我完全可以「自己走过去」——
//   走到一个格子，就立刻从它继续往四个方向走，走过的就染上色不再走。
//   这样每个格子只会被访问一次，一趟就能把整块走完。
//
//   O(Lnm)  →  O(nm)
//
// 而「走到一个格子，就从它继续往下走」这句话，翻译成代码就是函数调用自己 —— 递归。
// DFS 不是什么新东西，它就是第 1 章那个递归，只不过递归的对象从「数字」变成了「格子」。
//
// dfs(i, j) 的含义：我现在站在格子 (i,j) 上，负责把和它连通的、还没染色的陆地全部染上色。

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

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

int n, m;
vector<string> g;
vector<vector<char>> vis;

void dfs(int i, int j) {
    vis[i][j] = 1;                       // 先给脚下这格染色
    for (int d = 0; d < 4; d++) {        // 再看四个方向
        int x = i + dx[d], y = j + dy[d];
        if (x < 0 || x >= n || y < 0 || y >= m) continue;   // 出界
        if (g[x][y] != '1') continue;                        // 是水
        if (vis[x][y]) continue;                             // 已经染过了
        dfs(x, y);                                           // 走过去，重复同样的事
    }
}

int main() {
    if (!(cin >> n >> m)) return 0;
    g.resize(n);
    for (int i = 0; i < n; i++) cin >> g[i];
    vis.assign(n, vector<char>(m, 0));

    int blocks = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '1' && !vis[i][j]) {
                blocks++;      // 每发起一次 dfs，就意味着发现了一块新的
                dfs(i, j);
            }
        }
    }

    cout << blocks << "\n";
    return 0;
}

点一下即可编辑

这几个错误几乎人人都犯过，故意试一次：

把 vis[i][j] = 1; 那行删掉 → 相邻格子互相无限调用，对拍会报「超时」（其实是栈溢出）
方向数组写成八连通（对角线也算相邻）→ 第 1 轮就被抓
漏掉一个方向（比如只写上下左） → 第 1 轮就被抓
忘了判断出界 → 数组越界，对拍会报「异常退出」

✓ 注意生成器为什么这么造

这里的生成器故意让陆地和水各占一半。如果陆地占 90%，整张图基本就是一大块，那种数据太温柔，什么错都查不出来。

一半一半才会造出细长、分叉、犬牙交错的形状 —— 这才是能逼出 bug 的数据。 造数据的原则永远是：逼着程序走它平时不走的路。

11一个必须知道的坑：递归深度

⚠ 大网格上 DFS 会爆栈

DFS 的递归深度最坏等于连通块的格子数。刚才那条 200×200 的蛇形长廊，深度就有两万层。栈默认只有 8MB，一层几十字节，几万层还扛得住，但如果是 1000×1000 的大图（最坏一百万层），程序会直接崩溃 —— 而且不报任何错。

竞赛里遇到大网格，有三条路：

改用 BFS（下一章），用队列代替递归栈，堆内存管够；
手写栈把递归改成循环；
在支持的评测机上开大栈空间。

入门阶段记住结论就行：网格大到几十万格以上时，优先用 BFS。

12自测

自测清单0 / 7

合上页面，白纸默写 dfs 染色的完整代码（含方向数组和主函数循环）把默写的贴进对拍器，300 轮通过说得出 DFS 的「边界」藏在哪里（提示：三个 continue）说得出为什么「发起 dfs 的次数」就等于「连通块数」故意删掉 vis 标记跑一次，解释清楚为什么会栈溢出说得出什么情况下不该用 DFS 而该用 BFS完成下面至少 2 道练习题

配套练习

洛谷 P1596 Lake Counting S 解析 →　—— 本章模板题，只是改成八连通 —— 改方向数组即可
洛谷 P1451 求细胞数量解析 →　—— 和本章几乎一模一样，先拿它练手
洛谷 P1162 填涂颜色解析 →　—— 要从「外面」往里染色 —— 想想为什么不能从里面开始
洛谷 P1706 全排列问题解析 →　—— 回头复习第 3 章：确认自己看得出它和本章是同一个 DFS

这一章我卡在哪（过一个月回来看，这几行比整章正文都值钱）

下一章预告

第 14 章用同一张地图问一个不同的问题：从左上角走到右下角最少要几步？ DFS 在这个问题上会彻底翻车（7×7 的空网格就要枚举五亿七千万条路），而 BFS 只需要扫一遍格子。