【题目描述】

输入一个n×n的黑白图像（1表示黑色，0表示白色），任务是统计其中黑色连通块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个联通块。如下图所示的图形有3个联通块。

【输入描述】

【输出描述】

【样例输入】

6  100100  001010  000000  110000  111000  010100

【样例输出】

3

【题目分析】

1. 双队列版本，对比以前的单队列多了一个队列。

2. 每遇到一个点，就调用广搜函数，处理当前这个连通块，并增加连通块计数

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();  	}  }

【后续改进】

1. 可以使用pair进行改进