题解 P2864 【[USACO06JAN]树林The Grove】

· · 题解

为什么每人发题解？

来发Pascal

当然这是BFS的题。但是怎么BFS呢？我们要绕这个树林走一圈，而裸的BFS实现不了。怎么办？

都说了只是裸的BFS过不了而已。现在来讲正解：

我们随便挑一棵树，在它的右边往下建一堵“墙”。比如样例，如下图所示：

棕色的表示选的那棵树，在他右边往下面建一堵墙。

建了这堵墙以后，BFS时我们就强制让它不穿过这堵墙。

我们在BFS时，用a[i,j]表示从起点出发（不穿过墙）的最短路径（最少步数）。

比如样例（墙就建在那个地方），a数组的值应该是：

  8  7  6  5  5  5  5
  8  7  6 -1  4  4  4
  8  7 -1 -1 -1  3  3
  8  8  8 -1 -1 -1  2
  9  9  9 -1  2  1  1
 10 10 10  3  2  1  0

最后我们再把墙拆掉，两边能连起来的最小的和就是答案。具体见程序

献上我那丑陋的代码：

uses math;
const //坐标增量，八个方向
  dx:array[1..8]of -1..1 = (-1,0,1,0,-1,-1,1,1);
  dy:array[1..8]of -1..1 = (0,-1,0,1,-1,1,-1,1);
var
  n,m,i,j,sx,sy,zx,zy,h,t,ans:longint; //sx,sy是起点，zx,zy是“墙”的位置
  b:array[0..51,0..51]of boolean;
  a:array[0..51,0..51]of longint;
  q:array[0..10001,1..2]of longint;
  c:char;
procedure bfs(x,y:longint);
var
  k,i,j:longint;
begin
  h:=0; t:=1; q[t,1]:=x; q[t,2]:=y; b[x,y]:=false; a[x,y]:=0;
  while h<t do 
    begin
      inc(h); x:=q[h,1]; y:=q[h,2];
      if (x>=zx) and (y=zy) then continue; //如果在墙相邻的左边，这个值就不应该扩展
      for k:=1 to 8 do 
        begin
          i:=x+dx[k]; j:=y+dy[k];
          if (i>0) and (i<=n) and (j>0) and (j<=m) and b[i,j] then 
            begin
              if (i>=zx) and (j=zy) and (dy[k]=-1) then continue; //墙相邻的右边其实不能过来
              a[i,j]:=a[x,y]+1; b[i,j]:=false;
              inc(t); q[t,1]:=i; q[t,2]:=j;
            end;
        end;
    end;
end;
begin
  randomize;
  readln(n,m);
  for i:=0 to n+1 do 
    for j:=0 to m+1 do 
      a[i,j]:=-1; //全部置为-1，处理边界问题和树林
  for i:=1 to n do 
    begin
      for j:=1 to m do 
        begin
          read(c);
          if c='*' then begin sx:=i; sy:=j; end;
          if c='X' then b[i,j]:=false else b[i,j]:=true;
        end;
      readln;
    end;
  repeat zx:=random(n)+1; zy:=random(m)+1; until not b[zx,zy];
  bfs(sx,sy);
  writeln(zx,' ',zy);
  for i:=1 to n do 
    begin
      for j:=1 to m do write(a[i,j]:3);
      writeln;
    end;
  ans:=maxlongint shr 1;
  for i:=zx+1 to n do 
    if a[i,zy]>=0 then //不是树林
      for j:=-1 to 1 do 
        if a[i+j,zy+1]>=0 then ans:=min(ans,a[i,zy]+a[i+j,zy+1]); //不是树林也没有超出（超出自动是-1，上面说过了），比较出较小值
  write(ans+1); //起点本身加上去
end.