P1451 calculate the number of cells / 1329: [example 8.2] cells

This program is in CSDN Force list Ranking the first 15！！！

Pay attention to it

 P1451 Find the number of cells /​​​​​​1329：【 example 8.2】 cells

# Find the number of cells

## Title Description

A rectangular array consists of numbers $0$ To $9$ form , Numbers $1$ To $9$ For cells , Cell is defined as the number of cells, up and down, left and right. If it is still a cell number, it is the same cell , Find the number of cells in a given rectangular array .

## Input format

The two integers in the first line represent the size of the matrix $n$ and $m$.

Next $n$ That's ok , One length per line is $m$ The contains only characters `0` To `9` String , On behalf of the $n \times m$ Matrix .

## Output format

An integer in a row represents the number of cells .

## Examples #1

### The sample input #1

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

### Sample output #1

```
4
```

## Tips

#### Data scale and agreement

about $100\%$ The data of , Guarantee $1 \le n,m \le 100$.

1329：【 example 8.2】 cells

The time limit : 1000 ms         Memory limit : 65536 KB
Submission number : 19435     Passing number : 10979

【 Title Description 】

A rectangular array consists of numbers 00 To 99 form , Numbers 11 To 99 For cells , A cell is defined as the same cell along the cell number, up and down, left and right, or cell number , Find the number of cells in a given rectangular array . Such as :

array

4 10 0234500067 1034560500 2045600671 0000000089

Yes 44 Cells .

【 Input 】

The first row is the row of the matrix nn And column mm;

Here's a n×mn×m Matrix .

【 Output 】

Number of cells .

【 sample input 】

4 10
0234500067
1034560500
2045600671
0000000089

【 sample output 】

4

【 Algorithm analysis 】

（1） Read in... From a file n*m Matrix array , Put it Convert to boolean matrix Deposit in a Array in ;

（2） Along the a Array matrix From top to bottom 、 From left to right , Find what you encounter The first cell ;

（3） Put the position of the cell into team b, And along it 、 Next 、 Left 、 Right Four directions Cell location on The team , The position after joining the team a Array Set as false;

（4） take b The team's Team leader out of team , Along it 、 Next 、 Left 、 Right Four directions Cell location on The team , The position after joining the team a Array Set as false;

（5） repeat （4）, until b team So far , Now find A cell ;

（6） repeat （2）, Up to matrix Can't find cells ;

（7） Output the number of cells found .

【AC Code （ Array mock queue ）】

#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;// The first cell you encounter joins the team  
	do
	{
		i++;// Team leader pointer plus 1 
		for(int k=0;k<4;k++)// Search for cells in the up, down, left, right directions  
		{
			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;// Judge whether this point can join the team  
		}
	}while(i<j);// Don't miss the semicolon  
}
signed main()
{
	n=fread(),m=fread();
	memset(a,1,sizeof a);// initialization  
	/*
	 Another way to initialize ： 
	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;
}
// Hum, hum, this evil bfs The template stuck me all day 

Hum, hum, this evil bfs The template stuck me all day  

Pay attention to it

Pay attention to it