42. 求细胞数量
题目ID：8112必做题100分
最新提交：
Runtime Error
0 分
历史最高：
Runtime Error
0 分
时间限制: 100ms
空间限制: 131072kB
题目描述
一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
输入格式
第一行两个整数代表矩阵大小 n 行和 m 列。（1≤ n,m ≤ 100）
接下来 n 行，每行一个长度为 m 的只含字符 0 到 9 的字符串，代表这个 n×m 的矩阵。
输出格式
一个整数代表细胞的个数。
样例
Input 1
4 10 0234500067 1034560500 2045600671 0000000089
Output 1
4
数据范围
1≤ m, n ≤ 100
#include<stdio.h>
struct z{
int x,y;
}q[30000];
bool map[200][200],p[200][200];
int n,m,ans,c[4][2]={0,1,1,0,-1,0,0,-1};
char a;
void bfs(int x,int y){
ans++;
int f=0,r=1,X,Y;
q[1].x=x;
q[1].y=y;
while(f<r){
f++;
X=q[f].x,Y=q[f].y;
p[X][Y]=1;
for(int i=0;i<4;i++){
int xx=X+c[i][0];
int yy=Y+c[i][1];
if(map[xx][yy]&&(!p[xx][yy])){
q[++r].x=xx;
q[r].y=yy;
}
}
}
}
int main(){
scanf("%d %d",&m,&n);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a);
map[i][j]=(a!='0');
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(!p[i][j]&&map[i][j]){
bfs(i,j);
}
}
}
printf("%d",ans);
}
