侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS】求细胞数量

GabrielxD
2022-12-19 / 0 评论 / 0 点赞 / 16 阅读 / 446 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-19,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

P1451 求细胞数量


题目描述

一矩形阵列由数字 0099 组成,数字 1199 代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 nnmm

接下来 nn 行,每行一个长度为 mm 的只含字符 09 的字符串,代表这个 n×mn \times m 的矩阵。

输出格式

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

样例 #1

样例输入 #1

4 10
0234500067
1034560500
2045600671
0000000089

样例输出 #1

4

提示

数据规模与约定

对于 100%100\% 的数据,保证 1n,m1001 \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;
}
0

评论区