求细胞数量

题目

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

思路

简单的BFS。
从\((1,1)\)开始枚举到\((n,m)\)，只要其中某一个字符不是0，那就进行BFS。
BFS流程如下：

1. 存入b[1],c[1]（分别表示坐标x,y）
2. 从此处往四个方向枚举并把此处标记为-1
3. 枚举到非零的，重复1，2，3
4. 如果l>r，退出

• 写的有点草了，要有一定BFS的基础才能看懂

代码

#include<bits/stdc++.h>
using namespace std;

int n,m,ans,a[104][104];
char ch;
int b[10004],c[10004];
int di[5]={0,-1,0,0,1};
int dj[5]={0,0,-1,1,0};
void bfs(int x,int y)
{
	int l=1,r=1;
	b[1]=x;c[1]=y;
	while(l<=r)
	{
		for(int k=1;k<=4;k++)
		{
			int xx=b[l]+di[k],yy=c[l]+dj[k];
			if(a[xx][yy]<=0 || xx<1 || xx>n || yy<1 || yy>m)continue;
			r++;
			a[xx][yy]=-1;
			b[r]=xx;c[r]=yy;
			// cout<<xx<<" "<<yy<<endl;
		}
		l++;
	}
	if(r>=1)ans++;
	// cout<<r<<endl;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>ch,a[i][j]=ch-‘0‘;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]>0)
				/*cout<<i<<" "<<j<<endl,*/bfs(i,j);
	cout<<ans;

	return 0;
}

求细胞数量

原文：https://www.cnblogs.com/wuzhenhao/p/14955978.html