USACO2.1 城堡The Castle

城堡

題目描述

我們憨厚的USACO主人公農夫約翰(Farmer John)以無法想象的運氣,在他生日那天收到了一份特别的禮物：一張“幸運愛爾蘭”（一種彩票）。結果這張彩票讓他獲得了這次比賽唯一的獎品——坐落于愛爾蘭郊外的一座夢幻般的城堡！

喜歡吹噓的農夫約翰立刻回到有着吹噓傳統的威斯康辛老家開始吹噓了, 農夫約翰想要告訴他的奶牛們關于他城堡的一切。他需要做一些吹噓前的準備工作：比如說知道城堡有多少個房間，每個房間有多大。另外，農夫約翰想要把一面單獨的牆（指兩個機關間的牆）拆掉以形成一個更大的房間。 你的工作就是幫農夫約翰做以上的準備，算出房間數與房間的大小。

城堡的平面圖被劃分成M*N(1 <=M,N<=50）個正方形的機關，一個這樣的機關可以有0到4面牆環繞。城堡周圍一定有外牆環繞以遮風擋雨。（就是說平面圖的四周一定是牆。）

請仔細研究下面這個有注解的城堡平面圖：

友情提示，這個城堡的平面圖是7×4個機關的。一個“房間”的是平面圖中一個由“#”、“-”、“|”圍成的格子（就是圖裡面的那一個個的格子）。比如說這個樣例就有5個房間。（大小分别為9、7、3、1、8個機關（排名不分先後））

移去箭頭所指的那面牆，可以使2個房間合為一個新房間，且比移去其他牆所形成的房間都大。（原文為：Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall. ）

城堡保證至少有2個房間，而且一定有一面牆可以被移走。

分析：搜尋，把屬于同一個的點标記，在另一個數組裡存每個點所屬房間的大小，最後枚舉每個點，看拆除一面牆後兩個房間合并的最大值是否大于max。

代碼

const

  maxn=50;

  dx:array[1..4] of -1..1=(-1,0,1,0);

  dy:array[1..4] of -1..1=(0,1,0,-1);

var

  a:array[0..maxn,0..maxn,1..4] of boolean;

  b,c:array[0..maxn,0..maxn] of longint;

  f:array[0..maxn,0..maxn] of boolean;

  sum:array[0..5000] of longint;

  n,m,i,j,x,max,ans1,ans2,ansx,ansy:longint;

  ansd:char;

function check(x,y,x1,y1,d:longint):boolean;

begin

  check:=true;

  inc(d);

  if d>4 then d:=1;

  if (f[x,y]) or (a[x1,y1,d]) then exit(False);

end;

procedure dfs(x,y:longint);

var

  i:longint;

begin

  for i:=1 to 4 do

    if check(x+dx[i],y+dy[i],x,y,i) then

      begin

        inc(max);

        f[x+dx[i],y+dy[i]]:=true;

        dfs(x+dx[i],y+dy[i]);

      end;

  c[x,y]:=ans2+1;

end;

begin

  readln(m,n);

  for i:=1 to n do

    for j:=1 to m do

      begin

        read(x);

        if x>=8 then begin dec(x,8);a[i,j,4]:=true;a[i+1,j,2]:=true;end;

        if x>=4 then begin dec(x,4);a[i,j,3]:=true;a[i,j+1,1]:=true;end;

        if x>=2 then begin dec(x,2);a[i,j,2]:=true;a[i-1,j,4]:=true;end;

        if x>=1 then begin dec(x);a[i,j,1]:=true;a[i,j-1,3]:=true;end;

      end;

  for i:=1 to n do

    for j:=1 to m do

      if not f[i,j] then

        begin

          max:=1;

          f[i,j]:=true;

          dfs(i,j);

          inc(ans2);

          sum[ans2]:=max;

          if max>ans1 then ans1:=max;

        end;

  writeln(ans2);

  writeln(ans1);

  max:=0;

  for i:=1 to n do

    for j:=1 to m do

      b[i,j]:=sum[c[i,j]];

  for i:=1 to m do

    for j:=n downto 1 do

      begin

        if a[j,i,2] then

          if (b[j,i]+b[j-1,i]>max) and (j<>1) and (c[j,i]<>c[j-1,i])then

            begin

              max:=b[j,i]+b[j-1,i];

              ansd:='N';

              ansx:=j;

              ansy:=i;

            end;

        if a[j,i,3] then

          if (b[j,i]+b[j,i+1]>max) and (i<>m) and (c[j,i]<>c[j,i+1]) then

            begin

              max:=b[j,i]+b[j,i+1];

              ansd:='E';

              ansx:=j;

              ansy:=i;

            end;

      end;

  writeln(max);

  writeln(ansx,' ',ansy,' ',ansd);

end.