P1451 求细胞数量/​​​​​​1329：【例8.2】细胞

本程序猿在CSDN原力榜排名第15！！！

给个关注吧

 P1451 求细胞数量/​​​​​​1329：【例8.2】细胞

# 求细胞数量

## 题目描述

一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

## 输入格式

第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 `0` 到 `9` 的字符串，代表这个 $n \times m$ 的矩阵。

## 输出格式

一行一个整数代表细胞个数。

## 样例 #1

### 样例输入 #1

```
4 10
0234500067
1034560500
2045600671
0000000089
```

### 样例输出 #1

```
4
```

## 提示

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$。

1329：【例8.2】细胞

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 19435     通过数: 10979

【题目描述】

一矩形阵列由数字00到99组成,数字11到99代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:

阵列

4 10 0234500067 1034560500 2045600671 0000000089

有44个细胞。

【输入】

第一行为矩阵的行nn和列mm;

下面为一个n×mn×m的矩阵。

【输出】

细胞个数。

【输入样例】

4 10
0234500067
1034560500
2045600671
0000000089

【输出样例】

4

【算法分析】

（1）从文件中读入n*m矩阵阵列，将其转换为boolean矩阵存入a数组中；

（2）沿a数组矩阵从上到下、从左到右，找到遇到的第一个细胞；

（3）将细胞的位置入队b，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置a数组置为false；

（4）将b队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置a数组置为false；

（5）重复（4），直至b队空为止，则此时找出了一个细胞；

（6）重复（2），直至矩阵找不到细胞；

（7）输出找到的细胞数。

【AC代码（数组模拟队列）】

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int N=1e3+10;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
void fwrite(int n)
{
	if(n>9)fwrite(n/10);
	putchar(n%10+'0');
}
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},a[N][N],ans,n,m;
char ch[N],c;
void bfs(int x,int y)
{
	int z,p,i=0,j=1,b[N][3];
	ans++,a[x][y]=0,b[1][1]=x,b[1][2]=y;//遇到的第一个细胞入队 
	do
	{
		i++;//队头指针加1 
		for(int k=0;k<4;k++)//沿细胞的上下左右四个方向搜索细胞 
		{
			z=b[i][1]+dx[k],p=b[i][2]+dy[k];
			if(z>=0 and z<n and p>=0 and p<m and a[z][p])j++,b[j][1]=z,b[j][2]=p,a[z][p]=0;//判断该点是否可以入队 
		}
	}while(i<j);//别漏了分号 
}
signed main()
{
	n=fread(),m=fread();
	memset(a,1,sizeof a);//初始化 
	/*
	另一种初始化的方式： 
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)a[i][j]=1;
	*/
	for(int i=0;i<n;i++)
	{
		cin>>ch;
		for(int j=0;j<m;j++)
			if(ch[j]=='0')a[i][j]=0;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(a[i][j])bfs(i,j);
	fwrite(ans); 
	return 0;
}
//嘤嘤嘤这道万恶的bfs模板卡了我一整天

嘤嘤嘤这道万恶的bfs模板卡了我一整天 

给个关注吧

给个关注吧