P1451 求细胞数量

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

说明/提示

数据规模与约定

对于 \(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）：为了防止这个细胞在后续遍历中被重复计算，我们从这个格子开始启动 DFS（深度优先搜索），向上下左右四个方向蔓延。只要遇到的也是非 0 数字，就把它直接变成 0（或者打上已访问的标记）。 * 继续扫描：等 DFS 结束时，这一整片连通的细胞都已经被“抹除”成 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 × 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，继续找下一个。

我更喜欢用记忆化数组vis[ ][ ]

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

using namespace std;

int n, m;
vector<string> mp;
bool vis[20][20]; // 假设最大地图为 20x20
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int ans = 0;

// DFS 函数：用于标记当前岛屿的所有部分
void dfs(int x, int y) {
    // 边界检查、是否已访问、是否是水（'0'）
    if (x < 0 || y < 0 || x >= n || y >= m || vis[x][y] || mp[x][y] == '0') {
        return;
    }

    vis[x][y] = true; // 标记当前格点已访问

    // 向四个方向递归探索
    for (int i = 0; i < 4; i++) {
        dfs(x + dx[i], y + dy[i]);
    }
}

int main() {
    // 1. 读取行数和列数
    if (!(cin >> n >> m)) return 0;

    // 2. 正确读取地图数据
    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        mp.push_back(row);
    }

    // 3. 遍历地图上的每一个点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 如果发现一块未访问过的陆地（非 '0'）
            if (mp[i][j] != '0' && !vis[i][j]) {
                ans++;       // 发现一个新岛屿，计数加 1
                dfs(i, j);   // 使用 DFS 淹没/标记整个岛屿
            }
        }
    }

    // 4. 输出结果
    cout << ans << endl;

    return 0;
}