试题3 (注:本题初中生做):海海爱研究
海海是个爱研究的孩子,最近他在研究这么一个问题:一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:
阵列
4 10
0234500067
1034560500
2045600671
0000000089
有4个细胞。
【输入说明】
第1行是两个整数m,n(m≤50,n≤80),接下来m行每行有n个数字。
【输出说明】
细胞数量。
【样例输入】
4 10
0234500067
1034560500
2045600671
0000000089
【样例输出】
4
【算法分析】
(1) 读入m*n矩阵阵列,将其转换为boolean矩阵存入bz数组中;
(2) 沿bz数组矩阵从上到下,从左到右,找到遇到的第一个细胞;
(3) 将细胞的位置入队h,并沿其上、下、左、右四个方向上的细胞位置入队,入队后的位置bz数组置为flase;
(4) 将h队的队头出队,沿其上、下、左、右四个方向上的细胞位置入队,入队后的位置bz数组置为flase;
(5) 重复4,直至h队空为止,则此时找出了一个细胞;
(6) 重复2,直至矩阵找不到细胞;
(7) 输出找到的细胞数。
【程序清单】
PROGRAM ZX2017P8;
const dx:array[1..4 of -1..1=(-1,0,1,0);
dy:array[1..4 of -1..1=(0,1,0,-1);
var
s:string;
pic:array[1..50,1..80] of integer;
bz: array[1..50,1..80] of boolean;
m,n,i,j,num: integer;
h:array[1..4000,1..2]of integer;
procedure doit(p,q:integer);
var i,t,w,x,y:integer;
begin
inc(num);
bz[p,q]:=false;
t:= i; w:=1; h[1,1]:=p; h[1,2]:=q;
repeat
for i :=1 to 4 do
begin
x:=h[t,1]+dx[i];
y:=h[t,2]+dy[i];
if (x>0) and (x<=m) and (y>0) and (y<=n) and bz[x,y] then
begin
inc(w);
h[w,1]:=x;
h[w,2]:=y;
bz[x,y]:=false;
end;
end;
inc(t);
until t>w;
end;
begin
fillchar(bz,sizeof(bz),true);
num:=0;
readln(m,n);
for i :=1 to m do
begin
readln(s)
for j:=l to n do
begin
pic[i,j]:=ord(s[j]) - 48;
if pic[i,j]=0 then
bz[i,j]:=false;
end;
end;
for i :=1 to m do
for j :=1 to n do
if bz[i,j] then
doit(i,j);
writeln(num);
end.