洛谷 P1451 求细胞数量

洛谷 P1451 求细胞数量

---

题目

题目描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。（1<=m,n<=100）?

输入输出格式

输入格式：
输入：整数m,n(m行，n列)

矩阵

输出格式：

输出：细胞的个数

输入输出样例

输入样例#1：

4 10
0234500067
1034560500
2045600671
0000000089

输出样例#1：

4

---

题解

BFS，求联通块的个数

---

代码（Pascal）

const flag:array[1..4,0..1]of longint=((0,1),(1,0),(0,-1),(-1,0));
var n,m,head,tail,ans:longint;
    q:array[0..10005]of record
                           x,y:longint;
end;
    vis:array[0..105,0..105]of boolean;
procedure init;
var i,j:longint;
      ch:char;
begin
     fillchar(vis,sizeof(vis),0);
     readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ch);
if ch='0' then vis[i,j]:=true;
end;
        readln;
end;
end;
function check(x,y:longint):boolean;
begin
if (x<1)or(y<1)or(x>n)or(y>m)or(vis[x,y]=true) then exit(false);
exit(true);
end;
procedure find(x,y:longint);
begin
    inc(tail);vis[x,y]:=true;
    q[tail].x:=x;q[tail].y:=y;
end;
procedure bfs(x,y:longint);
var i:longint;
begin
     head:=0;tail:=1;
     q[1].x:=x;q[1].y:=y;
while head<tail do
begin
        inc(head);
        x:=q[head].x;y:=q[head].y;
for i:=1 to 4 do
if check(x+flag[i,0],y+flag[i,1]) then find(x+flag[i,0],y+flag[i,1]);
end;
end;
procedure main;
var i,j,x,y,z,w:longint;
      s:char;
begin
     ans:=0;
for i:=1 to n do
for j:=1 to m do
if vis[i,j]=false then begin
                                bfs(i,j);
                                inc(ans);
end;
end;
procedure print;
begin
write(ans);
end;
begin
   init;
   main;
   print;
end.