求细胞数量

形式化题目

给定一个 $n \times m$ 的字符网格，每个格子是字符 0 到 9 中的一个。字符不是 0 的格子称为细胞格子。若两个细胞格子的行号相同且列号相差 $1$ ，或列号相同且行号相差 $1$ （即上下左右相邻），则认为它们属于同一个细胞；细胞是细胞格子在四方向相邻关系下的极大连通集合。求网格中细胞的数量。

题面样例是一个 $4 \times 10$ 的网格，答案为 $4$ ，具体是哪四个细胞见下文 ### 思路 中的网格图。

正解

思路

把网格看成一张图：每个细胞格子是一个点，上下左右相邻的两个细胞格子之间连一条边。于是题目问的就是这张图的连通块个数。

数连通块不存在更弱的直接做法：任何正确算法都必须至少看过每个细胞格子一次，而洪水填充（Flood Fill）在 $O(nm)$ 的时间里同时完成「遍历」与「计数」，它既是朴素想法也是最终做法，没有「慢暴力 → 快优化」的演进过程。所以本文不设暴力层，brute.cpp 只是一份独立的并查集实现，专门用来自动对拍。

关键观察：扫描时遇到还没被访问过的细胞格子，它必然开启一个新的细胞。

已经数过的细胞会在搜索过程中被整体清空，网格上不再留下它的格子；
于是按行优先扫描时，凡是还留着的细胞数字，都不可能属于任何已经数过的细胞；
因此「遇到非 0 格 → 答案加一 → 搜索淹掉整个连通块」既不会重复计数，也不会漏计数。

实现上有三个不显然的决定：

只向四方向扩展。细胞只按上下左右粘连，斜对角接触不算。
原地标记。「是 0 还是非 0」正是「有没有细胞」的判据，所以每访问一格就把它改成 0，标记访问和清空格子合成一步，省掉单独的 vis 数组。
入队前就标记，而不是出队时标记。这样同一个格子最多入队一次，队列里不会出现重复副本。

下面这张图用题面样例展示搜索的结果，. 表示 0，相同字母表示同一个细胞：

text

1
2
3
4
5初始网格                      搜索后（同一字母 = 同一细胞）
0 2 3 4 5 0 0 0 6 7           . B B B B . . . C C
1 0 3 4 5 6 0 5 0 0           A . B B B B . D . .
2 0 4 5 6 0 0 6 7 1           A . B B B . . D D D
0 0 0 0 0 0 0 0 8 9           . . . . . . . . D D

观察三点：

C 的格子 $(1,9),(1,10)$ 与 D 的格子 $(2,8)$ 只是斜对角接触，中间隔着 $(2,9)$ 的 0，所以四方向下它们是两个细胞。若按八方向，C 与 D 会合成一个，答案就不是 $4$ 了——方向数组必须严格取上下左右。
扫描到 $(1,2)$ 时答案加一，搜索把 B 的 $11$ 个格子全部改成 0；继续扫描到 $(1,9)$ 时它还是非 0，说明 C 是新细胞，答案再加一。此时网格中已经没有属于 B 的格子，这正是上面那条关键观察。
扫描到 $(4,9)$ 时，它在 D 里的上邻居 $(3,9)$ 早已被改成 0，所以 $(4,9)$ 不会独立成细胞，而是和 $(3,9)$ 同属 D：新细胞只由「扫描时还是非 0」决定，不需要额外判断相邻关系。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 21:06
 * update_at: 2026-10-09 21:12
 */
// main.cpp：P1451 求细胞数量。
/* 扫描网格，每遇到一个还没被访问过的细胞数字，就用上下左右 BFS 淹掉整个细胞，答案加一。 */
// 代码分层：读入 / 洪水填充 / 统计输出各一个函数，main 只按顺序调用；
// 网格、方向数组、答案这些核心数据放全局，函数之间共享，比一大段 main 清楚。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;            // 网格行数、列数
// n,m <= 100，格子下标最多 104，答案最多 10^4，都在 int 范围内，所以网格和计数器用 int，不做类型转换
char g[MAXN][MAXN];  // g[i][j]：'1'..'9' 是细胞数字，'0' 不是细胞
int dx[4] = { -1, 1, 0, 0 }; // 四方向：上下左右（细胞只按上下左右粘连，不含对角线）
int dy[4] = { 0, 0, -1, 1 };

int ans; // 细胞个数，等于 BFS 启动的次数

// 读入 n、m 和 n 行长度为 m 的字符串
// 网格下标从 1 开始，扩展时判边界只要和 1、n、m 比大小
void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> (g[i] + 1); // 第 i 行整体读成字符串，直接写进 g[i][1..m]
    }
}

// 从 (sx, sy) 出发，把属于同一个细胞的所有格子都改成 '0'
// 直接改写网格，标记访问和清空细胞合成一步，省掉单独的 vis 数组
void flood_fill(int sx, int sy) {
    queue<pair<int, int>> q;
    g[sx][sy] = '0'; // 入队前就标记，保证每个格子最多入队一次
    q.push(make_pair(sx, sy));

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

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] != '0') {
                g[nx][ny] = '0';
                q.push(make_pair(nx, ny));
            }
        }
    }
}

// 按行优先扫一遍网格：此时还留着的细胞数字，都不可能属于之前的细胞
void solve() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] != '0') { // 还没被淹掉，从这里开始就是一个新细胞
                ans++;
                flood_fill(i, j);
            }
        }
    }
}

void output() {
    cout << ans << '\n';
}

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

    read_input();
    solve();
    output();

    return 0;
}

STL 写法

上面的 main.cpp 用固定数组 char g[105][105] 存网格，队列里放 pair<int, int> 这样一对坐标。C++ 里还有更省事的写法：网格用 vector<string>，一行就是一个 string，cin >> grid[x] 直接整行读入，不必关心字符数组末尾的 \0；队列里只存压平下标 idx = x * m + y，一个 int 就能定位格子，不用再开 queue<pair<int, int>>。

压平带来的直接好处是「上下左右」变成四个固定偏移量：

方向	偏移量	越界判断
上	`idx - m`	`x > 0`
下	`idx + m`	`x + 1 < n`
左	`idx - 1`	`y > 0`
右	`idx + 1`	`y + 1 < m`

注意左右两个偏移量会跨行：第 $0$ 列的 idx - 1 恰好是上一行的最后一格。所以左右方向必须先用 y = idx % m 还原列号，判掉 $y = 0$ 和 $y = m-1$ 两种情况；上下方向加减一整行仍落在同一列，只需判行号 $x$ 的边界。

还有一点值得强调：网格本身就是图，两格是否相邻可以直接由下标算出来，不需要像普通图论题那样先建邻接表再遍历。vector<string> 同时充当了「图」和「访问标记」：搜索过的格子一律改成 '0'，和 main.cpp 的处理完全一致。

对应的 cppbook 章节：vector：能改变长度的数组、string：把字符串当作可操作的数据、queue：先进先出

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 21:12
 * update_at: 2026-10-09 21:12
 */
// main-stl.cpp：P1451 求细胞数量（STL 写法）。
// 做法和 main.cpp 一样：扫描网格，遇到还没被访问过的细胞数字就开始一个新的细胞计数，
// 从它出发 BFS，把上下左右相连的细胞数字全部访问掉。
// STL 版的差别在数据结构：
//   * 网格用 vector<string> 存，一行就是一个 string，读入时整行读进 grid[x]；
//   * BFS 队列里只存压平下标 idx = x * m + y，一个下标就能定位格子，
//     不用再开 queue<pair<int,int>>；
//   * 网格本身就是图，相邻关系能直接算出来，不需要建邻接表。
// 代码分层：读入 / 搜索 / 输出各一个函数，main 只按顺序调用；
// 网格、规模、答案这些核心数据放全局，函数之间共享。
#include <bits/stdc++.h>
using namespace std;

int n, m;            // 网格行数、列数
// n,m <= 100，压平下标 idx = x * m + y <= 10^4，答案 <= 10^4，都在 int 范围内，一律用 int，不做类型转换
vector<string> grid; // grid[x]：第 x 行字符串，grid[x][y] != '0' 表示这一格是细胞
int ans;             // 细胞个数，等于 BFS 启动的次数

// 读入 n、m 和 n 行字符串
// 下标从 0 开始，和 vector、string 的天然下标一致，不用再为边界做什么偏移
void read_input() {
    cin >> n >> m;
    grid.assign(n, "");
    for (int x = 0; x < n; x++) {
        cin >> grid[x]; // 一行读成一个 string，长度保证是 m
    }
}

// 从压平下标 start 出发，把属于同一个细胞的所有格子都改成 '0'
// 压平后上下左右是四个固定偏移：idx - m、idx + m、idx - 1、idx + 1
void flood_fill(int start) {
    queue<int> q;
    grid[start / m][start % m] = '0'; // 入队前就标记，保证每个格子最多入队一次
    q.push(start);

    while (!q.empty()) {
        int idx = q.front();
        q.pop();

        int x = idx / m; // 由压平下标还原出当前的行、列
        int y = idx % m;

        // 上下：加减一整行仍然落在同一列，不会跨行
        if (x > 0 && grid[x - 1][y] != '0') {
            grid[x - 1][y] = '0';
            q.push(idx - m);
        }
        if (x + 1 < n && grid[x + 1][y] != '0') {
            grid[x + 1][y] = '0';
            q.push(idx + m);
        }
        // 左右：必须用列号判断是否跨行，否则行首的 idx - 1 会跑到上一行行尾
        if (y > 0 && grid[x][y - 1] != '0') {
            grid[x][y - 1] = '0';
            q.push(idx - 1);
        }
        if (y + 1 < m && grid[x][y + 1] != '0') {
            grid[x][y + 1] = '0';
            q.push(idx + 1);
        }
    }
}

// 按行优先扫一遍网格：此时还留着的细胞数字，都不可能属于之前数过的细胞
void solve() {
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            if (grid[x][y] != '0') { // 还没被淹掉，从这里开始就是一个新细胞
                ans++;
                flood_fill(x * m + y); // 行列压平成下标，交给 BFS
            }
        }
    }
}

void output() {
    cout << ans << '\n';
}

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

    read_input();
    solve();
    output();

    return 0;
}

复杂度

时间：每个格子最多入队、出队一次，再加上一遍全网格扫描， $O(nm)$ ；对 $1 \leqslant n,m \leqslant 100$ 的数据，最坏只有 $10^4$ 个格子。
空间：网格本身与最坏情况下装下整个网格的 BFS 队列， $O(nm)$ 。
STL 写法的复杂度完全相同：vector<string> 与压平下标都没有改变每个格子的处理次数。

总结

统计连通块是一类固定套路：发现一个未访问的目标点，答案加一，再搜索并标记整个连通块。本题只是把「相邻」定义为上下左右四方向，并把网格本身当成图来遍历——这正是 Flood Fill 模板最典型的形状。

main.cpp 用固定数组加 queue<pair<int, int>>，是最贴近模板、也最容易在赛场上手写出来的版本；main-stl.cpp 把网格换成 vector<string>、把坐标压平成一个下标，代码更短，同时说明「网格即图」这件事：相邻关系能直接算出来，不需要建邻接表。两者做法一致、复杂度一致，可以用 brute.cpp（并查集）作为独立基线互相验证。

图遍历的 visited 标记与队列分层扩展可参考 rbook 的《图的遍历》，队列的用法见《队列》。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20题意：四方向相邻的非 '0' 格构成一个细胞，数细胞个数
        |
        | 关键观察：扫描到的第一个未访问非 '0' 格，必然属于新细胞
        v
Flood Fill（main.cpp：char 数组 + queue<pair<int,int>>）
   扫描全网格
   |-- 格子是 '0'：跳过
   `-- 格子非 '0'：答案 +1，从它开始 BFS
        向 4 个方向（不含对角）扩展
        入队前把格子改成 '0'（原地标记，省掉 vis 数组）
        |
        v
STL 写法（main-stl.cpp：vector<string> + queue<int>）
   网格 grid[x] 是 string，队列存压平下标 idx = x * m + y
   上下左右 = idx -/+ m、idx -/+ 1，左右用 y = idx % m 判断是否跨行
   网格本身就是图，不建邻接表
        |
        v
答案 = BFS 启动的次数
每个格子最多进出队一次：时间 O(n*m)，空间 O(n*m)

图中三条主线分别对应「为什么扫到非 0 格就能确定是新细胞」「搜索时有哪些容易写错的边界」「STL 写法换了哪些数据结构」。整道题的难点只落在三个细节：方向必须是四个而不是八个、标记要和清空合并成一步、以及压平下标后左右方向要防跨行。

目录

形式化题目

正解

思路

代码

STL 写法

复杂度

总结

图示解析