跳转至

P1451 求细胞数量

题目描述

一矩形阵列由数字 \(0\) 到 \(9\) 组成，数字 \(1\) 到 \(9\) 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 \(n\) 和 \(m\)。

接下来 \(n\) 行，每行一个长度为 \(m\) 的只含字符 0 到 9 的字符串，代表这个 \(n \times m\) 的矩阵。

输出格式

一行一个整数代表细胞个数。

输入输出样例 #1

输入 #1

4 10
0234500067
1034560500
2045600671
0000000089

输出 #1

4

说明/提示

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1 \le n,m \le 100\)。

Tip

b站讲解链接

📌 题目分析

给定数据：

n 行 m 列的矩阵 (1 ≤ n, m ≤ 100)
由字符 '0' 到 '9' 组成

其中 1 到 9 代表细胞实体，0 代表空白。上下左右相邻的数字属于同一个细胞。求总共有多少个独立的细胞。

👉 本质：

求二维网格中的连通块数量

👉 类型：

深度优先搜索 (DFS) / 广度优先搜索 (BFS) / Flood Fill (洪水填充算法)

🧠 解题思路

1️⃣ 经典 Flood Fill 算法

想象一下你在用 Windows 画图工具，用“油漆桶”工具在一个封闭的图形里点一下，颜色就会瞬间填满整个图形。 这就是 Flood Fill 的核心逻辑。

对于这道题，我们可以在网格里进行扫描： * 寻找起点：利用两层 for 循环遍历每一个格子。如果遇到一个不为 0 的格子，说明我们发现了一个新细胞，计数器加一。 * 感染/消除（DFS/BFS）：为了防止这个细胞在后续遍历中被重复计算，我们从这个格子开始启动 DFS（深度优先搜索），向上下左右四个方向蔓延。只要遇到的也是非 0 数字，就把它直接变成 0（或者打上已访问的标记）。 * 继续扫描：等搜索结束时，这一整片连通的细胞都已经被“抹除”成 0 了。双重循环继续往下找，直到整个网格都被扫完。

2️⃣ 边界与方向控制

在二维网格中上下左右移动，通常会使用方向数组来简化代码，而不是写四个臃肿的 if：

int dx[4] = {-1, 1, 0, 0}; // 行的变动：上下左右
int dy[4] = {0, 0, -1, 1}; // 列的变动：上下左右

每次移动后，必须检查新坐标 (nx, ny) 是否越界：

nx >= 0 且 nx < n 且 ny >= 0 且 ny < m

3️⃣ 时间复杂度

表面上看起来有两层 for 循环加上一个递归 dfs，像是有三层嵌套。 但实际上，网格中的每一个格子最多只会被访问和变为 0 一次。 因此总时间复杂度严格与网格大小成正比：

\(O(n \times m)\)

最大 \(100 \times 100 = 10000\) 次操作，耗时不到 1 毫秒，极其高效。

💻 C++代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, m;
vector<string> grid;

// 方向数组：上、下、左、右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

// 深度优先搜索，用于“抹除”连通块
void dfs(int x, int y) {
    // 1. 将当前访问的细胞标记为 '0'，避免重复访问
    grid[x][y] = '0';

    // 2. 遍历四个方向寻找相邻的细胞部分
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 3. 检查是否越界，且新位置是否也是细胞 ('1'~'9')
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '0') {
            dfs(nx, ny); // 继续深入蔓延
        }
    }
}

int main() {
    // 优化输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    grid.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i]; // 一次读取一整行字符串
    }

    int cell_count = 0;

    // 遍历整个网格寻找细胞的起点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 如果遇到不为 '0' 的字符，说明找到了新细胞
            if (grid[i][j] != '0') {
                cell_count++; // 细胞数量 +1
                dfs(i, j);    // 启动 DFS 将这个细胞所在的连通块全部变为 '0'
            }
        }
    }

    cout << cell_count << "\n";

    return 0;
}

⚠️ 易错点

❌ 1. 输入数据的读取陷阱

题目输入格式中，每一行的数字是连在一起没有空格的：

0234500067

如果你用二维的 int 数组 cin >> matrix[i][j] 来读取，C++ 会把这一整行直接当成一个超大整数吃进去，导致错误。 正确做法：必须使用 string 或者 char 数组，逐行读取字符串，或者逐个字符读取。

❌ 2. 忘记将格子重置或标记

在 dfs 开始时，必须立刻执行 grid[x][y] = '0';。 如果只是遍历而不修改它的值，在 A 走到 B 后，B 找四周时又会走回 A，从而引发死循环，最终导致内存爆满（Stack Overflow / RE）。

❌ 3. 斜向不连通

题目严格规定：“沿细胞数字上下左右若还是细胞数字则为同一细胞”。 也就是说对角线方向（左上、左下、右上、右下）是不互通的。如果习惯了八方向的搜索题，方向数组别不小心开成了 8 个。

🚀 一句话总结

遇到非 0 就计数加一，然后一发 DFS 洪水填充把连通的格子全抹平为 0，继续找下一个。

🔥 补充：硬核知识点

同一道题的不同视角：DFS vs BFS vs 并查集

这道题其实是图论中非常核心的“求连通分量”问题。除了我们代码中写的 DFS，它还有两种经典的降维打击视角：

  1. BFS (广度优先搜索) 视角
  2. 区别：DFS 是一条路走到黑，BFS 则是用水波扩散的方式一层层往外找。

  3. 优劣：这道题 \(N \le 100\)，DFS 的递归深度最大一万层，勉强不会爆栈。但如果数据范围拉大到 \(N \le 2000\)，DFS 会因为调用栈太深直接导致程序崩溃（RE）。而 BFS 依赖的是 std::queue，内存在堆区 (Heap) 分配，绝不会爆栈。在真正的工业级代码中，Flood Fill 通常优先使用 BFS。

  4. 并查集 (Disjoint Set Union, DSU) 视角

  5. 思路：一开始，假设网格里所有的非 0 数字都是互相独立的“单身汉”。我们遍历网格，每次检查当前格子的“右边”和“下边”。如果邻居也是非 0，我们就把这两个格子“合并”到同一个集合里。
  6. 优劣：全部合并完后，只要数一数并查集里有几个“祖宗节点”，就能得出有几个独立的细胞。这种写法完全避开了搜索与递归，常用于动态连通性问题（比如：如果细胞是动态一个个长出来的，问某个时刻有几个连通块，DFS/BFS 每次都要重新搜，而并查集可以 \(O(1)\) 瞬间给出答案）。