一道几乎是模板dfs的题目 https://www.luogu.com.cn/problem/P1451

求细胞数量

题目描述

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

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

cpp
#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> matrix;
vector<vector<bool>> visited;

// 方向数组，用于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;
    
    matrix.resize(n, vector<int>(m));
    visited.resize(n, vector<bool>(m, false));
    
    // 读取矩阵
    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;
int n,m,ans=0;
int a[105][105];
bool used[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y)
{
	used[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(a[nx][ny]==0 || used[nx][ny]==1) continue;
		dfs(nx,ny);
	}
}
int main()
{
	cin>>n>>m;
	memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) 
			scanf("%1d",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(used[i][j]==0 && a[i][j]!=0)
			{
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans;	
	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;
}

目录