目录

• 一 问题描述
• 二 解题思路 
• 三 核心代码 
• 四 完整代码 
• 五 注意点 

---

一 问题描述

 

例子如下：输入4行10列的矩阵，根据题意，可以数出在该例子中细胞数目共有4个

  

如下：输入3行10列的矩阵，根据题意，可以数出在该例子中细胞数目共有1个

二 解题思路 

该题可以使用广度优先搜索算法（BFS）来做，我们以图1为例讲一讲解题思路

        通过观察，可以发现，被0单独围起来的数字区域总共有4个，因此该图的细胞数为4，利用BFS将每一个数字区域中1-9之间的数进行扫描，然后将数值全部赋值为某个非1-9之间的数，比如说-1。每当扫描完一个区域，我们便将细胞的计数器+1，单个区域的扫描可以通过BFS函数来实现，在这里，我将这个函数取名为scan，在主函数中，找出所有的1-9数值之间的元素，每判断到当前元素的值在1-9之间，便调用scan函数进行单个区域的扫描和赋值，也就是意味着，scan被调用了几次，那么最终图中的细胞数就会有几个。

---

        在主函数中找出数值在1-9之间的元素，从此元素出发，调用scan函数，寻找数值区域，将数值区域重新赋值，并且细胞计数器+1

        第一次：从a[0][0]开始判断，发现a[0][0]中的数值不在1-9之间，说明从当前点出发并无数字区域可以扫描，因此找寻下一个元素a[0][1]，找到a[0][1]的时候发现，它的数值落在1-9范围之内，说明从当前点a[0][1]出发有数字区域可以扫描，于是调用scan函数，将此元素的下标位置(0,1)作为参数传递给scan函数，于是scan函数就从(0,1)开始进行数字区域的扫描，scan函数就是利用了BFS的思想，将从(0,1)出发的数字区域进行扫表，并且扫描过后该区域所有的元素都被赋值为-1（也可以是别的，只要不在1-9范围内即可），代表该区域已经被访问过，细胞计数器+1，此时，数据变为：

        第二次：刚刚上一步a[0][1]已经访问过了，并且a[0][1]出发的区域也已经被全部扫描过了，可以通过上图看出来，接下去在主函数中应该是要判断a[0][2]这个元素了，我们可以发现，此时a[0][2]这个元素中的数值已经被上一次的区域扫描而被赋值成1了，因此并不会调用scan函数，在主函数中继续遍历a[0][3],a[0][4]，发现他们两个都是-1，所以scan函数也不会被调用，继续扫描a[0][5]，发现a[0][5]的值是0，所以从这个点出发也不会有数据区域，依此类推，当遍历到a[0][8]的时候，发现它的数值落在1-9范围之间，那就可以从此元素出发，调用scan函数，将(0,8)这个下标作为参数传递给scan函数，在scan函数中进行BFS扫描，并且将从这个点出发扫描后的数字区域全部赋值为-1，代表该区域已经被访问过了，细胞计数器+1，此时，数据变为：

        第三次：刚刚上一步a[0][8]已经访问过了，接下来继续访问a[0][9]，发现它的值为-1，受了上一个数据区域扫描的影响，在主函数中，我们判断过后，它的值不在1-9这个范围之内，我们可以不再访问，依次类推，当在主函数中访问到a[1][0]，发现它的值落在1-9范围之间，那么从这个元素出发，进行BFS的扫描，将下标(1,0)传递给scan函数，此时scan函数被调用，然后在scan函数中从(1,0)出发，扫描1所在的那个数据区域，并将扫描过的元素都被赋值为-1，代表该区域也已经被访问过了，细胞计数器+1，此时，数据变成：

        第四次：刚刚上一步a[1][0]已经被访问过了，继续访问a[1][1],a[1][2],a[1][3]......a[1][6]，发现它们都不满足调用scan函数的条件，因为范围都不在1-9之内，当访问到a[1][7]的时候，发现它的数值5落在1-9范围之内，于是从下标(1,7)出发，调用scan函数，在scan函数中从(1,7)出发，扫描5所在的那个数据区域，并且将扫描过后的元素全部赋值为-1，代表该区域已经被访问过了，细胞计数器的值+1，此时数据变为：

        第五次：按照上面的规律，不断在主函数中遍历元素，如果当前元素的数值落在1-9之间，那么就从这个元素出发，遍历这个元素所在的数字区域，并且将这个数字区域中的数值全部赋值为非1-9之间的数，那么最终，主函数中scan函数调用了几次，细胞数就会统计到几个。

三 核心代码 

//用来存放数据 
int a[65][65];
int m,n,sum=0;

struct Point
{
	int x;
	int y;
};
queue<struct Point> q;
void scan(int i,int j)
{
	int k,ni,nj;
	int dx[4]={-1,1,0,0};
	int dy[4]={0,0,-1,1};
	struct Point p;
	p.x=i; p.y=j;
	q.push(p); 
	while(!q.empty())  
	{
		p=q.front(); 
		q.pop(); 
		i=p.x; j=p.y;
		if(a[i][j]>=1&&a[i][j]<=9)  //数值为1-9代表没有访问过，访问过的点无需再进行重复的扩展 
		{
			a[i][j]=-1;  //给-1代表已经访问过
			//遍历上下左右四个方向
			for(k=0;k<=3;k++)
			{
				ni=i+dx[k];
				nj=j+dy[k];
				//前面两个控制越界，访问过的不再访问，元素为0也不能放进去,放进去的只能是1-9之间的元素 
				if(1<=ni&&ni<=m&&1<=nj&&nj<=n&&(a[ni][nj]!=-1&&a[ni][nj]!=0)) 
				{
					p.x=ni; p.y=nj;
					q.push(p);	
				}	
			} 
		} 
	}
		sum++;
	
} 

 

四 完整代码 

#include<bits/stdc++.h>
using namespace std;

//用来存放数据 
int a[65][65];
int m,n,sum=0;

struct Point
{
	int x;
	int y;
};
queue<struct Point> q;
void scan(int i,int j)
{
	int k,ni,nj;
	int dx[4]={-1,1,0,0};
	int dy[4]={0,0,-1,1};
	struct Point p;
	p.x=i; p.y=j;
	q.push(p); 
	while(!q.empty())  
	{
		p=q.front(); 
		q.pop(); 
		i=p.x; j=p.y;
		if(a[i][j]>=1&&a[i][j]<=9)  //数值为1-9代表没有访问过，访问过的点无需再进行重复的扩展 
		{
			a[i][j]=-1;  //给-1代表已经访问过
			//遍历上下左右四个方向
			for(k=0;k<=3;k++)
			{
				ni=i+dx[k];
				nj=j+dy[k];
				//前面两个控制越界，访问过的不再访问，元素为0也不能放进去,放进去的只能是1-9之间的元素 
				if(1<=ni&&ni<=m&&1<=nj&&nj<=n&&(a[ni][nj]!=-1&&a[ni][nj]!=0)) 
				{
					p.x=ni; p.y=nj;
					q.push(p);	
				}	
			} 
		} 
	}
		sum++;
	
} 
int main()
{
	//freopen("cell.in","r",stdin);  //别忘记，文件里面放的数据没有用空格隔开 
	cin>>m>>n;
	char q[65][65];
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>q[i][j];	
			a[i][j]=q[i][j]-'0';
		}	
	} 
	
		

	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]>=1&&a[i][j]<=9)
			{
					scan(i,j);
			}
					
		}
	}

	cout<<sum;
	return 0;
}

 

五 注意点 

1.遍历过后的数据区域要记得重新赋值为非1-9之间的数值

2.要去遍历数据数组中的每一个元素，不能够只遍历边缘或者某一部分数据，如下图：如果你只遍历边缘元素，那么按照上面的思路，最终程序的结果只会输出0，并不会得到预想的结果1，因为如果只遍历边缘，那么scan函数一次都不会被执行，这就错了！！！

3.计数器记得初始化为0

4.输入的时候记得对输入数据进行处理，看下图，输入的时候，数据区域部分是字符型的数据，需要将字符型的数据转换成整型数据

代码如下：