问题描述
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 如: 阵列 4 10 0234500067 1034560500 2045600671 0000000089 有4个细胞。 按照上下左右的顺序进行检查,并将符合条件的依次入队
算法分析
⑴从文件中读入m*n矩阵阵列，将其转换为boolean矩阵存入bz数组中； ⑵沿bz数组矩阵从上到下，从左到右，找到遇到的第一个细胞； ⑶将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为false； ⑷将h队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为false； ⑸重复4，直至h队空为止，则此时找出了一个细胞； ⑹重复2，直至矩阵找不到细胞； ⑺输出找到的细胞数。
代码实现
#include<cstdio>
using namespace std
;
int dx
[4]={-1,0,1,0},
dy
[4]={0,1,0,-1};
int bz
[100][100],num
=0,n
,m
;
void doit(int p
,int q
){
int x
,y
,t
,w
,i
;
int h
[1000][2];
num
++;
bz
[p
][q
]=0;
t
=0;w
=1;
h
[1][1]=p
; h
[1][2]=q
;
do {
t
++;
for (i
=0;i
<=3;i
++){
x
=h
[t
][1]+dx
[i
];
y
=h
[t
][2]+dy
[i
];
if ((x
>=0)&&(x
<m
)&&(y
>=0)&&(y
<n
)&&(bz
[x
][y
])){
w
++;
h
[w
][1]=x
; h
[w
][2]=y
; bz
[x
][y
]=0;
}
}
}while (t
<w
);
}
int main(){
int i
,j
;
char s
[100],ch
;
scanf("%d%d\n",&m
,&n
);
for (i
=0; i
<=m
-1;i
++ )
for (j
=0;j
<=n
-1;j
++ )
bz
[i
][j
]=1;
for (i
=0;i
<=m
-1;i
++) {
gets(s
);
for (j
=0;j
<=n
-1;j
++) if (s
[j
]=='0') bz
[i
][j
]=0;
}
for (i
=0;i
<=m
-1;i
++)
for (j
=0;j
<=n
-1;j
++)
if (bz
[i
][j
]) doit(i
,j
);
printf("NUMBER of cells=%d",num
);
return 0;
}
