【题解】黑色联通块
【题目描述】
输入一个n×n的黑白图像（1表示黑色，0表示白色），任务是统计其中黑色连通块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个联通块。如下图所示的图形有3个联通块。
【输入描述】
第1行输入一个正整数n（n≤700），此后输入n行，每行是由n个0或1组成的字符串。
【输出描述】
输出连通块的个数
【样例输入】
6 100100 001010 000000 110000 111000 010100
【样例输出】
3
【题目分析】
双队列版本，对比以前的单队列多了一个队列。
每遇到一个点，就调用广搜函数，处理当前这个连通块，并增加连通块计数
bfs思路是不断从队列中取出像素，检查其8个方向的邻居：如果邻居是黑色且未被访问，则将其加入队列，并标记为已访问。直到队列为空，表示当前连通块已全部遍历
【整体思路】
1.遍历图像：逐行逐列遍历图像中的每个像素。
2.发现黑色像素：如果发现一个未被访问过的黑色像素，启动 BFS 或 DFS 来标记所有与之相连的黑色像素。
3.计数连通块：每次启动 BFS 或 DFS 时，增加连通块的计数。
【参考代码】
#include<iostream>
#include<queue>
#include<cstdio>
#define maxn 750
using namespace std;
int n,sum=0;
int a[maxn][maxn];
int x[8]={0,0,1,1,1,-1,-1,-1};
int y[8]={1,-1,-1,0,1,-1,0,1};
void bfs(int,int);
string s;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s;
for(int j=0;j<n;j++) a[i][j+1]=s[j]-48; //字符转数字
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==1)
{
bfs(i,j);
sum++;
}
}
}
cout<<sum;
return 0;
}
void bfs(int i,int j)
{
queue<int> qi,qj; //分别存储当前连通块中像素的行和列索引
qi.push(i);
qj.push(j);
a[i][j]=0;
while(!qi.empty())
{
int ki=qi.front(),kj=qj.front();
for(int i=0;i<8;i++)
{
int kx=ki+x[i],ky=kj+y[i];
if(kx>=1&&kx<=n&&ky>=1&&ky<=n)
{
if(a[kx][ky]==1)
{
a[kx][ky]=0;
qi.push(kx);
qj.push(ky);
}
}
}
qi.pop();
qj.pop();
}
}【后续改进】
可以使用pair进行改进
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
