当前位置:网站首页>P1451 求细胞数量/1329:【例8.2】细胞
P1451 求细胞数量/1329:【例8.2】细胞
2022-07-05 14:47:00 【暴揍键盘的程序猿】
本程序猿在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模板卡了我一整天
边栏推荐
- Stm32+bh1750 photosensitive sensor obtains light intensity
- Interview shock 62: what are the precautions for group by?
- 在Pytorch中使用Tensorboard可视化训练过程
- [recruitment position] Software Engineer (full stack) - public safety direction
- 机器学习笔记 - 灰狼优化
- webRTC SDP mslabel lable
- 超级哇塞的快排,你值得学会!
- 729. My schedule I: "simulation" & "line segment tree (dynamic open point) &" block + bit operation (bucket Division) "
- 【jvm】运算指令
- Online electronic component purchasing Mall: break the problem of information asymmetry in the purchasing process, and enable enterprises to effectively coordinate management
猜你喜欢
亿咖通科技通过ISO27001与ISO21434安全管理体系认证
Niuke: intercepting missiles
How to choose the appropriate certificate brand when applying for code signing certificate?
微帧科技荣获全球云计算大会“云鼎奖”!
leetcode:881. 救生艇
729. My schedule I: "simulation" & "line segment tree (dynamic open point) &" block + bit operation (bucket Division) "
Chow Tai Fook fulfills the "centenary commitment" and sincerely serves to promote green environmental protection
Pointer operation - C language
【华为机试真题详解】字符统计及重排
FR练习题目---简单题
随机推荐
SSL证书错误怎么办?浏览器常见SSL证书报错解决办法
在Pytorch中使用Tensorboard可视化训练过程
Penetration testing methodology
Isn't it right to put money into the external market? How can we ensure safety?
Talking about how dataset and dataloader call when loading data__ getitem__ () function
CODING DevSecOps 助力金融企业跑出数字加速度
机器学习笔记 - 灰狼优化
anaconda使用中科大源
Want to ask the big guy, is there any synchronization from Tencent cloud Mysql to other places? Binlog saved by Tencent cloud MySQL on cos
Drive brushless DC motor based on Ti drv10970
Behind the ultra clear image quality of NBA Live Broadcast: an in-depth interpretation of Alibaba cloud video cloud "narrowband HD 2.0" technology
Microframe technology won the "cloud tripod Award" at the global Cloud Computing Conference!
be careful! Software supply chain security challenges continue to escalate
[recruitment position] infrastructure software developer
Longest common subsequence dynamic programming
Stm32+bh1750 photosensitive sensor obtains light intensity
Topology visual drawing engine
TS所有dom元素的类型声明
NBA赛事直播超清画质背后:阿里云视频云「窄带高清2.0」技术深度解读
Reconnaissance des caractères easycr