求细胞数量

题目描述

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

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

直接dfs

cpp
#include <iostream>
using namespace std;

int n, m;
int matrix[105][105];
bool visited[105][105];

// 方向数组，用于DFS遍历上下左右四个方向
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// DFS函数
void dfs(int x, int y) {
    visited[x][y] = true;
    
    // 遍历四个方向
    for (int i = 0; i < 4; ++i) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        
        // 检查是否越界，是否是细胞数字，是否未访问过
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] != 0 && !visited[nx][ny]) {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    
    // 读取矩阵
    for (int i = 0; i < n; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < m; ++j) {
            matrix[i][j] = row[j] - '0';
        }
    }
    
    int cell_count = 0;
    
    // 遍历矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] != 0 && !visited[i][j]) {
                // 发现一个新的细胞
                dfs(i, j);
                cell_count++;
            }
        }
    }
    
    // 输出细胞总数
    cout << cell_count << endl;
    
    return 0;
}

大佬题解

cpp

#include <bits/stdc++.h>
using namespace std;
template <typename _Tp>
inline void read(_Tp &x){
    int w=1;char c=0;x=0;
    while (c^'-'&&(c<'0'||c>'9'))c=getchar();
    if (c=='-')w=-1,c=getchar();
    while (c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=w;
}
inline void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}//输入输出优化，请自动忽略
int n,m,ans,dx[]={-1,0,1,0},dy[]={0,-1,0,1},a[105][105];//a即地图，dx和dy方向增量数组就不用我讲了吧
void dfs(int x,int y){
	if (x>n||y>m||x<0||y<0)return;
	a[x][y]=0;//标记为没有
	for (int i=0;i<4;i++)if (a[x+dx[i]][y+dy[i]])dfs(x+dx[i],y+dy[i]);//如果有才搜
}//搜索
int main(){
	read(n),read(m);
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)scanf("%1d",&a[i][j]);//只读1位
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)if (a[i][j])ans++,dfs(i,j);//找
	write(ans);//输出
	return 0;
}

目录