P1451 求细胞数量
- 分析：根据题意，不为0的数连在一起是一个细胞，就是用bfs进行搜索，先是让初始点进入队列，记录下队头的点并向他的上下左右搜索，在没有越界且是细胞（不为0）的情况下，对这个细胞进行标记（后面搜的时候就不搜他了，要不然没完），这一点进行完之后将他放入队尾，在最后输出的时候如果一个点是细胞就标记上对他搜索一遍，这样他周围不为0的数也都被搜到，细胞数目就+1。
-
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int n,m,sum=0;
char s;
int a[101][101];//标记数组
int dx[4]={0,0,1,-1};//四个方位
int dy[4]={1,-1,0,0};
struct node
{
int x,y;
}now;
void bfs(int x,int y)
{
queue<node> q;
q.push({x,y});//讲初始点的入队
while(!q.empty())
{
now=q.front();//当前的点
q.pop();
for(int i=0;i<4;i++)
{
int xx=now.x+dx[i];//往当前点的各个方向前进
int yy=now.y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy])
{//未越界且是细胞
a[xx][yy]=0;//标记
q.push({xx,yy});//过完了之后放入队尾
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>s;
a[i][j]=s-'0';//将字符转换为整型
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!=0)//是细胞
{
a[i][j]=0;//标记
bfs(i,j);
sum++;
}
}
}
cout<<sum;
return 0;
}