当前位置:网站首页>P1451 calculate the number of cells / 1329: [example 8.2] cells
P1451 calculate the number of cells / 1329: [example 8.2] cells
2022-07-05 15:03:00 【A program ape who beats the keyboard violently】
This program is in CSDN Force list Ranking the first 15!!!
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
边栏推荐
- Mysql---- function
- 手写promise与async await
- 通过npm 或者 yarn安装依赖时 报错 出现乱码解决方式
- Jmeter性能测试:ServerAgent资源监控
- GPS原始坐标转百度地图坐标(纯C代码)
- 机器学习框架简述
- Super wow fast row, you are worth learning!
- What are the domestic formal futures company platforms in 2022? How about founder metaphase? Is it safe and reliable?
- Ecotone technology has passed ISO27001 and iso21434 safety management system certification
- I want to inquire about how to ensure data consistency when a MySQL transaction updates multiple tables?
猜你喜欢
qt creater断点调试程序详解
社区团购撤城“后遗症”
Ctfshow web entry explosion
[12 classic written questions of array and advanced pointer] these questions meet all your illusions about array and pointer, come on!
机器学习笔记 - 灰狼优化
Under the crisis of enterprise development, is digital transformation the future savior of enterprises
超越PaLM!北大硕士提出DiVeRSe,全面刷新NLP推理排行榜
PyTorch二分类时BCELoss,CrossEntropyLoss,Sigmoid等的选择和使用
Photoshop插件-动作相关概念-ActionList-ActionDescriptor-ActionList-动作执行加载调用删除-PS插件开发
做研究无人咨询、与学生不交心,UNC助理教授两年教职挣扎史
随机推荐
Handwriting promise and async await
Creation and use of thymeleaf template
爱可可AI前沿推介(7.5)
Select sort and bubble sort
729. 我的日程安排表 I :「模拟」&「线段树(动态开点)」&「分块 + 位运算(分桶)」
anaconda使用中科大源
There is a powerful and good-looking language bird editor, which is better than typora and developed by Alibaba
R 熵权法计算权重及综合得分
Un week - end heureux
【NVMe2.0b 14-9】NVMe SR-IOV
我这边同时采集多个oracle表,采集一会以后,会报oracle的oga内存超出,大家有没有遇到的?
CPU设计实战-第四章实践任务三用前递技术解决相关引发的冲突
PyTorch二分类时BCELoss,CrossEntropyLoss,Sigmoid等的选择和使用
Leetcode: Shortest Word Distance II
Ctfshow web entry information collection
[12 classic written questions of array and advanced pointer] these questions meet all your illusions about array and pointer, come on!
超级哇塞的快排,你值得学会!
1330:【例8.3】最少步数
Can I pass the PMP Exam in 20 days?
Stm32+bh1750 photosensitive sensor obtains light intensity