求细胞数量
题目链接
这道题大概是一个最简单的联通块的题了qwq
- 注意枚举起点的时候 一定不要从0开始不然你就会从0进入到了其他联通块中从而多查。
- 一定看清题意这道题不是同色为联通块！！！
AC代码如下：
其实里面联通块没有必要被涂成不同的颜色，所以也可以全部涂成一个颜色
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 3000
#define MEXN 100010
using namespace std;
int G[MAXN][MAXN];
int done[MAXN][MAXN];
int color=1;
struct item
{
int x;
int y;
};
queue<item>q;
int m,n;
void bfs(item t)
{
q.push(t);
while(!q.empty()){
item r;
r=q.front();
// printf( "x: %d, y: %d
", r.x, r.y );
// cout<<r.x<<endl;
// cout<<r.y<<endl;
q.pop();
if(done[r.x][r.y]!=0) continue;
done[r.x][r.y]=color;
if(G[r.x+1][r.y]!=0&&r.x+1<=m&&done[r.x+1][r.y]==0){
item t2;
t2.x=r.x+1;
t2.y=r.y;
q.push(t2);
}
if(G[r.x-1][r.y]!=0&&r.x-1>=1&&done[r.x-1][r.y]==0){
item t2;
t2.x=r.x-1;
t2.y=r.y;
q.push(t2);
}
if(G[r.x][r.y+1]!=0&&r.y+1<=n&&done[r.x][r.y+1]==0){
item t2;
t2.x=r.x;
t2.y=r.y+1;
q.push(t2);
}
if(G[r.x][r.y-1]!=0&&r.y-1>=1&&done[r.x][r.y-1]==0)
{
item t2;
t2.x=r.x;
t2.y=r.y-1;
q.push(t2);
}
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
char c;
scanf( " %c", &c );
// cin>>c;
G[i][j]=c-'0';
}
}
// for(int i=1;i<=m;i++)
// {
// for(int j=1;j<=n;j++)
// {
// printf("%d ",G[i][j]);
// }
// cout<<endl;
// }
int cnt=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(G[i][j]==0)continue;
item t;
t.x=i;
t.y=j;
if(done[i][j]==0)
{
cnt++;
color++;
bfs(t);
}
}
}
printf("%d",cnt);
return 0;
}