求细胞数量
题目描述
一矩形阵列由数字 0 0 0 到 9 9 9 组成，数字 1 1 1 到 9 9 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
输入格式
第一行两个整数代表矩阵大小 n n n 和 m m m。
接下来
n
n
n 行，每行一个长度为
m
m
m 的只含字符 0 到 9 的字符串，代表这个
n
×
m
n \times m
n×m 的矩阵。
输出格式
一行一个整数代表细胞个数。
样例 #1
样例输入 #1
4 10
0234500067
1034560500
2045600671
0000000089
样例输出 #1
4
提示
数据规模与约定
对于 100 % 100\% 100% 的数据，保证 1 ≤ n , m ≤ 100 1 \le n,m \le 100 1≤n,m≤100。
C++实现
#include
int n,m,a[101][101];
int tot=0,fa[10010],stlst,stnow,qj[10010][2];
int find(int u)
{
return u==fa[u]?u:fa[u]=find(fa[u]);
}
int main()
{
scanf(“%d%d”,&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf(“%1d”,&a[i][j]);
for(int i=1;(i<<1)<=n*m;i++) fa[i]=i;
for(int i=1;i<=n;i++)
{
stlst=stnow;
stnow=tot;
for(int j=1;j<=m;j++)
if(a[i][j])
{
qj[tot][0]=j;
while(a[i][j]) j++;
qj[tot][1]=j-1;
for(int k=stlst;k<stnow;k++)
if(qj[k][1]>=qj[tot][0]&&qj[k][0]<=qj[tot][1]) fa[find(k)]=tot;
tot++;
}
}
int ans=0;
for(int i=tot-1;i>=0;i–) if(fa[i]==i)
ans++;
printf(“%d”,ans);
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，感兴趣的请关注，我后续将继续分享相关内容
标签：P1451,int,细胞,tot,fa,C++,打卡,qj,100 From： https://blog.csdn.net/rogeliu/article/details/143449394