当前位置:首页 > 题解目录 > 正文内容

【题解】黑色联通块

亿万年的星光7个月前 (02-22)题解目录689

【题目描述】

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

【输入描述】

第1行输入一个正整数n(n≤700),此后输入n行,每行是由n个0或1组成的字符串。

【输出描述】

输出连通块的个数

【样例输入】

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进行改进


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】宴会

【题目描述】今人不见古时月,今月曾经照古人。梦回长安,大唐风华,十里长安花,一日看尽。 唐长安城是当时世界上规模最大、建筑最宏伟、规划布局最为规范化的一座都城。其营建 制度规划布局的特点是规...

【题解】Ride to Office

【题目描述】起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是,他有个习惯,沿途需要有人陪伴,即以相同的速度, 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时,他会以相应的速...

【动态规划】完全背包

【题目描述】设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为m,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于m,而价值的和...

【题解】木材加工

【题目描述】 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头(木头有可能有剩余),需要得到的小段的数目是事先给定的,切割时希望得到的小段越长越好。   ...

【题解】最多次数

【题目描述】小蓝有一个字符串 s,他特别喜欢由以下三个字符组成的单词:l,q,b,任意顺序都可以,一共有 6 种可能:lqb、lbq、qlb、qbl、blq、bql。现在...

【题解】网线主管

【题目描述】仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成,他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起,即将它们全部连到一个单一的中心服务器。为...