首页 > 代码库 > 【CodeVS】1293

【CodeVS】1293

技术分享

技术分享

输入输出样例

技术分享

思路:看到题目我萌第一眼想到的肯定是求联通快对吧,但是这个联通快有点奇特,因为

这样他也算是一个联通快技术分享。解决此题其实有三种解法:1)宽搜(这个符合基本法);2)并查集;3)灌水法

但是蒟蒻写的是并查集

代码如下:

 

技术分享
 1 var n,m,i,j,ans:longint;
 2     c:array[0..1000,0..1000]of char;
 3     pre:array[0..10000000]of longint;
 4     a:array[0..10000000]of boolean;
 5 function find(x:longint):longint;
 6 begin
 7  if pre[x]=x then exit(x);
 8  find:=find(pre[x]);
 9  pre[x]:=find;
10 end;
11 procedure join(x,y:longint);
12 var fx,fy:longint;
13 begin
14  fx:=find(x);fy:=find(y);
15  if fx<>fy then pre[fx]:=find(fy);
16 end;
17 begin
18  readln(n,m);
19  for i:=1 to n*m do pre[i]:=i;
20  for i:=1 to n do
21   begin
22    for j:=1 to m do
23     begin
24      read(c[i,j]);
25          if c[i,j]=# then a[(i-1)*m+j]:=true;
26          if c[i,j]=- then a[(i-1)*m+j]:=false;
27     end;
28     readln;
29   end;
30   for i:=1 to n do
31    begin
32     for j:=1 to m do
33      begin
34       if c[i,j]=# then
35       begin
36            if c[i+1,j]=# then join(i*m+j,(i-1)*m+j);
37            if c[i,j+1]=# then join((i-1)*m+j+1,(i-1)*m+j);
38             if c[i+2,j]=# then join((i+1)*m+j,(i-1)*m+j);
39             if c[i,j+2]=# then join((i-1)*m+j+2,(i-1)*m+j);
40             if c[i+1,j-1]=# then join(i*m+j-1,(i-1)*m+j);
41             if c[i+1,j+1]=# then join(i*m+j+1,(i-1)*m+j);//其实不用12个点全部判一遍,因为有重复覆盖到的部分
42       end;
43      end;
44    end;
45   for i:=1 to n*m do if pre[i]=i then if a[i] then inc(ans);//统计“联通快”个数
46  writeln(ans);
47 end.
View Code

 

这是蒟蒻第一道一次AC的提,发个随笔纪念一下(^_^)

 

【CodeVS】1293