TYVJ1137 英雄的yuan0818 — BFS+状态压缩

Note: 本文最初于 2011年02月21日 星期一 21:27 在 hi.baidu.com/lydrainbowcat 发表。

题目：http://www.tyvj.cn/p/1137

这题难在更新条件和状态比较繁琐……我交了4次，从40到80到90再到AC……

出题人原意是BFS+状态压缩，但是数据比较水，不压缩也能过……

1. 记录方式：

• f数组记录某个点上的最新锤子状态
• v记录某个点是否被访问到
• q:array[0..1000000]of record x,y,time:longint; end;队列
• d:记录队列中存储的某一步时锤子的状态，可以定义为一个二维的数组，不状态压缩直接用个boolean数组也能过。

2. 更新扩展条件：

一个点需要被扩展更新当且仅当满足下列任意一条即可：

• 该点未被扩展过(v[x,y]=false)
• 该点上f数组记录的当前最新锤子状态，与想要扩展更新的状态不同。

3. 更新

根据队首元素，更新队尾和扩展到的点的f和v数组。

4. 退出：

第一次搜到n,n时立即退出。

另一种思路，由杜神牛提出：将图每个锤子或者门看做一个点，然后用朴素的BFS（只处理0的）求出任意两个点之间的最短距离，然后再处理缩小后的只含有锤子和门的图。

type
 arr=array[0..50]of boolean;
const
 dx:array[1..4]of integer=(-1,0,0,1);
 dy:array[1..4]of integer=(0,-1,1,0);
var
 f:array[0..51,0..51]of arr;
 a:array[0..51,0..51]of longint;
 v:array[0..51,0..51]of boolean;
 q:array[0..1000000]of record x,y,t:longint; end;//一个点的状态要记录在队列里，否则会被其它更新扩展的点影响
 d:array[0..1000000]of arr;
 n,m,i,j,ans,x,y,l,r,k:longint;
procedure scanf;//读入特别需要注意，极易出错，不可以直接读然后-1的前后左右也-1。
 begin
  readln(n,m);
  for i:=0 to n+1 do
   for j:=0 to n+1 do a[i,j]:=-maxint;
  a[n,n]:=0;
  for i:=1 to n do
   begin
    for j:=1 to n do
     begin
      if (i=n)and(j=n) then break;
      read(k);
      if a[i,j]=-maxint then a[i,j]:=k;
      if k=-1 then
       begin
        a[i,j]:=-1;
        a[i-1,j]:=-1;
        a[i+1,j]:=-1;
        a[i,j-1]:=-1;
        a[i,j+1]:=-1;
       end;
    end;
   readln;
  end;
 end;
function diff:boolean;//更新条件
 var
  i:longint;
 begin
  if not v[x,y] then exit(true);
  for i:=1 to m+1 do
   if (not f[x,y,i])and d[l,i] then exit(true);
  exit(false);
 end;
procedure enter;//入队+更新扩展
 begin
  v[x,y]:=true;
  f[x,y]:=d[l];
  inc(r);
  q[r].x:=x;
  q[r].y:=y;
  q[r].t:=q[l].t+1;
  d[r]:=d[l];
 end;
procedure bfs;
 begin
  l:=1; r:=1;
  q[1].x:=1; q[1].y:=1; q[1].t:=0;
  v[1,1]:=true;
  if a[1,1]>m then//起点是锤子
   begin
    f[1,1,a[1,1]-m]:=true;
    d[1,a[1,1]-m]:=true;
   end;
  while l<=r do
   begin
    for i:=1 to 4 do
     begin
      x:=q[l].x+dx[i];
      y:=q[l].y+dy[i];
      if (x=n)and(y=n) then//已经到达终点
       begin
        ans:=q[l].t+1;
        exit;
       end;
      if (a[x,y]=0)and diff then enter;//是道路
      if (a[x,y]>m)and diff then//是锤子
       begin
        enter;
        d[r,a[x,y]-m]:=true;
        f[x,y]:=d[r];
       end;
      if (a[x,y]>0)and(a[x,y]<=m)and diff then//是门
       begin
        if (d[l,a[x,y]]) then enter;
        if (d[l,a[x,y]+1]) then enter;
       end;
     end;
    inc(l);
   end;
 end;
begin
 scanf;
 ans:=maxlongint;
 bfs;
 if ans=maxlongint then writeln(-1) else writeln(ans);
end.