USACO/castle

分析

'做法一：floodfill 选择最佳的墙来推倒。有多解时选（重心）最靠西的（仍然有多解时选这些里面（重心）最靠南的）。用该墙的南邻单位的北墙或西邻单位的东墙来表示这面墙，方法是输出邻近单位的行数、列数和墙的方位（"N"（北）或者"E"（东））。 (若按从西到东，从南到北顺序枚举不会出现这种情况for(int j=1;j<=m;++j)for(int i=n;i>=1;--i))

“有多解时选（重心）最靠西的（仍然有多解时选这些里面（'重心）最靠南的）。” 请注意重心二字！ 北墙的重心当然比东墙的要靠西啊~~

用一个二维数组记录每个格的四面是否有墙，根据输入，利用位运算得出每个格的墙的情况（8 = 2³,4 = 2²,2 = 2¹,1 = 2⁰）。 然后用floodfill，对每个房间染色，求出房间数，和每个房间的面积，输出其中最大的。

枚举每堵墙，如果墙的两边不是同一个房间且其面积和更大，更新结果，为了结果唯一，我们从左下向右上，一列一列枚举格子，并且先枚举该格上面的墙再枚举右边的。

墙 1：西，2:北，4：东；8：南 我们可以用一个三维的布尔型数组来判断有没有墙，false即为有墙，TRUE为无墙。 那么我们在读入时可以做以下操作：

fillchar(g,sizeof(g),1);
for i:=1 to n do
  for j:=1 to m do
    begin
     read(k);
     if k>=8 then begin dec(k,8);g[i,j,4]:=false;end;
     if k>=4 then begin dec(k,4);g[i,j,3]:=false;end;
     if k>=2 then begin dec(k,2);g[i,j,2]:=false;end;
     if k>=1 then begin dec(k,1);g[i,j,1]:=false;end;
    end;

注意顺序不能颠倒！（yearwhk：这个方法真的很巧妙！）

做法二：并查集 也是可以的嘛...WA AC～！ 判断墙的状况可以用位运算

做法三：连通分支 用链表记录，指针的元素记录下当前的行号列号与所指向的连通分支。

做法四：硬做 直接将输入转化为一个图，找联通块，然后输出最大的。判断两个联通块之间是否相邻，若是，则将他们合并的方式和合并后的尺寸与当前最大值相比较，选取较大的，打印，完事。。

做法五：正常做法 可以开个lv数组标记属于同一联通块的节点（每一次dfs前inc(shu)一次，然后将所有本次dfs到得节点做同样的标记），后直接判断连通性(lv[i]<>lv[j])，根本不用并查集（那是动态求解的数据结构），还可以直接将节点直接记录上最大空间（每dfs一次入栈和出栈）。 (jzoi)

……一种简易的判断语句……

function check(x,y,a:integer)
begin
if (map[x][y] div a) mod 2=1
  then exit(true)
else exit(false);
end;

可以在不影响源数据的情况下获得结果(……但是，这样有什么用么……)

代码

C

C++

Pascal

JAVA

引用

[1]

[2]