Poj2688 Cleaning Robot — 状态压缩BFS / BFS+TSP

Note: 本文最初于 2011年 在 hi.baidu.com/lydrainbowcat 发表。

两种思路：

1.直接状态压缩BFS，开一个[20,20,1024]数组记状态，但是要注意，由于一个case里有好多数据，所以：

不要fillchar队列数组，我fillchar=tle， 不fillchar=235ms

实在不行就把变量改到integer，不要用longint。

2.先BFS转化为tsp，然后用DP或者heap+a*解决tsp问题，但是我按这种思路写死活TLE。

两种思路都提供代码（第一种235ms，第二种TLE）：

Source Code

Problem: 2688		User: lydliyudong
Memory: 2032K		Time: 235MS
Language: Pascal		Result: Accepted

• Source Code

const
 dx:array[1..4]of integer=(-1,0,0,1);
 dy:array[1..4]of integer=(0,-1,1,0);
 a1:array[1..10]of integer=(1,2,4,8,16,32,64,128,256,512);
 a2:array[0..10]of integer=(0,1,3,7,15,31,63,127,255,511,1023);
var
 q:array[0..1000000]of record x,y,dat,vis:integer; end;
 num:array[0..20,0..20]of byte;
 v:array[0..20,0..20,0..1024]of boolean;
 a:array[0..21,0..21]of char;
 n,m,i,j,tot,ans,sx,sy:integer;

procedure scanf;
 begin
  for i:=0 to 21 do
   for j:=0 to 21 do a[i,j]:='x';
  tot:=0;
  for i:=1 to n do
   begin
    for j:=1 to m do
     begin
      read(a[i,j]);
      if a[i,j]='o' then begin sx:=i; sy:=j; end;
      if a[i,j]='*' then begin inc(tot); num[i,j]:=tot; end;
     end;
    readln;
   end;
 end;

procedure bfs;
 var
  l,r:longint;
  nx,ny,i:integer;
 begin
  fillchar(v,sizeof(v),0);
  l:=1; r:=1;
  q[1].x:=sx; q[1].y:=sy;
  v[sx,sy,0]:=true;
  while l<=r do
   begin
    for i:=1 to 4 do
     begin
      nx:=q[l].x+dx[i];
      ny:=q[l].y+dy[i];
      if (a[nx,ny]<>'x')and not v[nx,ny,q[l].vis] then
       begin
        inc(r);
        q[r].x:=nx;
        q[r].y:=ny;
        q[r].dat:=q[l].dat+1;
        q[r].vis:=q[l].vis;
        v[nx,ny,q[l].vis]:=true;
        if a[nx,ny]='*' then
         begin
          q[r].vis:=q[l].vis or a1[num[nx,ny]];
          if q[r].vis=a2[tot] then begin ans:=q[r].dat; exit; end;
         end;
       end;//if
     end;//for i
   inc(l);
   end;
 end;

begin
 repeat
  readln(m,n);
  if (n=0)and(m=0) then break;
  scanf;
  ans:=-1;
  bfs;
  writeln(ans);
 until seekeof;
end.

Source Code

Problem: 2688		User: lydliyudong
Memory: N/A		Time: N/A
Language: Pascal		Result: Time Limit Exceeded

• Source Code

const
 dx:array[1..4]of integer=(-1,0,0,1);
 dy:array[1..4]of integer=(0,-1,1,0);
 a1:array[1..10]of integer=(1,2,4,8,16,32,64,128,256,512);
 a2:array[0..10]of integer=(0,1,3,7,15,31,63,127,255,511,1023);
type
 rec=record x,y,dat:integer; end;
 heapqueue=record pos,dat,vis:longint; end;
var
 a:array[0..21,0..21]of char;
 b:array[0..10]of rec;
 q:array[0..500]of rec;
 map:array[0..10,0..10]of integer;
 v:array[0..21,0..21]of boolean;
 num:array[0..21,0..21]of integer;
 f:array[0..1000000]of heapqueue;
 n,m,i,j,k,ans,tab,p:longint;

procedure scanf;
 begin
  for i:=0 to 21 do
   for j:=0 to 21 do a[i,j]:='x';
  k:=0;
  for i:=1 to n do
   begin
    for j:=1 to m do
     begin
      read(a[i,j]);
      if a[i,j]='o' then begin b[0].x:=i; b[0].y:=j; end;
      if a[i,j]='*' then
       begin inc(k); b[k].x:=i; b[k].y:=j; num[i,j]:=k; end;
     end;
    readln;
   end;
 end;

procedure bfs(sx,sy,k:longint);
 var
  l,r,i,nx,ny:longint;
 begin
  fillchar(q,sizeof(q),0);
  fillchar(v,sizeof(v),0);
  l:=1; r:=1;
  q[1].x:=sx; q[1].y:=sy;
  v[sx,sy]:=true;
  if k=0 then tab:=0;
  while l<=r do
   begin
    for i:=1 to 4 do
     begin
      nx:=q[l].x+dx[i];
      ny:=q[l].y+dy[i];
      if (a[nx,ny]='*')and(not v[nx,ny]) then
       begin
        if k=0 then inc(tab);
        map[k,num[nx,ny]]:=q[l].dat+1;
        map[num[nx,ny],k]:=q[l].dat+1;
        if tab=k then exit;
       end;
      if (a[nx,ny]<>'x')and not v[nx,ny] then
       begin
        v[nx,ny]:=true;
        inc(r);
        q[r].x:=nx;
        q[r].y:=ny;
        q[r].dat:=q[l].dat+1;
       end;//if
     end;//for
    inc(l);
   end;
 end;

procedure swap(var x,y:heapqueue);
 var
  z:heapqueue;
 begin
  z:=x; x:=y; y:=z;
 end;

procedure insert;
 var
  i,t,now:longint;
 begin
  now:=f[1].vis;
  for i:=1 to k do
   begin
    if now and 1=0 then
     begin
      inc(p);
      f[p]:=f[1];
      f[p].pos:=i;
      inc(f[p].dat,map[f[1].pos,i]);
      f[p].vis:=f[p].vis or a1[i];
      t:=p;
      while t>1 do
       if f[t].dat<f[t div 2].dat then
        begin
         swap(f[t],f[t div 2]);
         t:=t div 2;
        end
      else break;
     end;
    now:=now shr 1;
   end;
 end;

procedure heapify(l,r:longint);
 var
  t:longint;
 begin
  t:=2*l;
  while t<=r do
   begin
    if (t<r)and(f[t].dat>f[t+1].dat) then inc(t);
    if f[l].dat>f[t].dat then
     begin
      swap(f[l],f[t]);
      l:=t; t:=2*l;
     end
    else break;
   end;
 end;

begin
 repeat
  readln(m,n);
  if (n=0)and(m=0) then break;
  fillchar(num,sizeof(num),0);
  scanf;
  if k=0 then begin writeln(0); continue; end;
  fillchar(map,sizeof(map),0);
  bfs(b[0].x,b[0].y,0);
  if tab<k then begin writeln(-1); continue; end else tab:=0;
  for i:=1 to k do bfs(b[i].x,b[i].y,i);
  ans:=-1;
  fillchar(f,sizeof(f),0);
  p:=1;
  while p>=1 do
   begin
    if f[1].vis=a2[k] then begin writeln(f[1].dat); break; end;
    insert;
    f[1]:=f[p]; dec(p); 
    heapify(1,p); 
   end;
 until false;
end.