【DFS】求细胞数量

题目

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$。

解题

方法一：DFS

思路

遍历矩阵，过程中如果遇到细胞部分就深搜出整个细胞，计数增加，并且标记处已经访问过的点以避免重复计数。

代码

#include <iostream>
#include <limits>

using namespace std;

const int N = 110, DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m;
bool g[N][N];
int cnt;

void dfs(int x, int y) {
    g[x][y] = false;
    for (auto& DIR: DIRS) {
        int nx = x + DIR[0], ny = y + DIR[1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny]) dfs(nx, ny);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        for (int j = 0; j < m; ++j) {
            char x;
            scanf("%c", &x);
            if (x != '0') g[i][j] = true;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j]) {
                dfs(i, j);
                ++cnt;
            }
        }
    }
    printf("%d\n", cnt);

    return 0;
}