洛谷 P1451 求细胞数量

时间:2023-01-11 19:45:54

题目大意:
求在一个很神奇的矩阵中,有多少个细胞,,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,细胞数字为1~9.

题解:
dfs:
1.每次找到未被遍历一个细胞数字的坐标进行搜索,记住数字不能为0。
2.以这个坐标为中心遍历与它相连的全部细胞数字赋值为遍历过。
3.累加细胞数量1,然后找下一个细胞数字。

var
a:Array [0..101,0..101] of char;
b:array [0..101,0..101] of boolean;
i,j,n,m,ans:longint;
s:string;

procedure dfs(x,y:longint);
begin
if (x<1) or (x>m) or (y<1) or (y>n) then exit;
if b[x,y]=false then exit;
b[x,y]:=false;
if a[x-1,y]=a[x,y] then dfs(x-1,y);
if a[x+1,y]=a[x,y] then dfs(x+1,y);
if a[x,y-1]=a[x,y] then dfs(x,y-1);
if a[x,y+1]=a[x,y] then dfs(x,y+1);
end;

begin
readln(m);
for i:=1 to m do
begin
readln(s);
n:=length(s);
for j:=1 to n do
if s[j]='0' then a[i,j]:='0'
else a[i,j]:='1';
end;
for i:=1 to m do
for j:=1 to n do b[i,j]:=true;
for i:=1 to m do
for j:=1 to n do
if (b[i,j]) and (a[i,j]<>'0') then
begin
inc(ans);
dfs(i,j);
end;
writeln(ans);
end.