Poj1475 Pushing Boxes — 双重BFS

Note: 本文最初于 2011年03月08日 星期二 17:36 在 hi.baidu.com/lydrainbowcat 发表。

šhttp://poj.org/problem?id=1475

š双重BFS(对箱子,对人)

š箱子的状态总数:坐标+方向,20*20*4。

š主框架是对箱子进行BFS,尝试向4个方向移动。若能移动,再对人BFS,检查人能否到达箱子的一侧把箱子推走。

š除了初始状态外,每次箱子移动后,人一定在箱子移动方向的后边邻格中。因此人的位置不必添加入总状态。

这里面注意两点,一是BFS人的时候要注意到当前箱子所在的地方是不可以走的;二是要满足“推箱子的次数最少”,推箱子次数一样时再走的步数最少。

在BFS判重时,对人,直接使用一个boolean数组,看某些点能不能到达。对箱子,看每个坐标上某一方向的状态是否以前拓展过,也就是[20,20,4]的数组,4指的是四个方向。

附几组数据:

11 19
....#####..........
....#...#..........
....#...#..........
..###..B##.........
..#......#.........
###.#.##.#...######
#...#.##.#####T...#
#.................#
####..###.#S##....#
...#......#########
...########........
Maze #1
nwwwnnnwwnneSwswssseeennnWWnwSSSnnwwssseEEEEEEEEEEseNenW

20 20
S...................
.##################.
..................#.
.#.#..............#.
.#.###########.#..#.
.#.#...........#..#.
.#.#..########.#..#.
.#.#.........#.#..#.
.#.########..#.#..#.
.#.#.....B...#.#....
.#.#.######..#.#..#.
.#.#.........#.#..#.
.#.#..########.#..#.
.#.#............#.#.
.#.#............#.#.
.#.#.############.#.
..................#.
.#................#.
.##################.
...................T
Maze #2
sssssssssssssssseeeennnnnnneeeeEEwwwwwwsseeeeeeenennwSSesWWWWWWWeeeeeennwwwwwwwsSSSSSnneeeeeeeeeennnnnnnnnnnwwwwwwwwwwwwsssssssssssssseEEEEEEEEEEEEEseNNNNNNNwnEEwnnnnnnnwwwwwwwwwwwwwwwwwnneeeeeeeeeeeeeeeeeeessssssssSSSSSSSSSS
20 20
S...................
.T..................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
..................B.
....................
Maze #1
essesesseeseseseeeesseeessssessessseeNNNNNNNNNNNNNNNNNenWWWWWWWWWWWWWWWWW

参考程序:

Source Code

Problem: 1475 User: lydliyudong
Memory: 3688K Time: 63MS
Language: Pascal Result: Accepted
    • Source Code
const
 dx:array[1..4]of integer=(-1,1,0,0);
 dy:array[1..4]of integer=(0,0,-1,1);
 dir:array[1..4]of char=('n','s','w','e');
var
 a:array[0..21,0..21]of char;
 q:array[0..100000]of record x,y,px,py,last:longint; str:ansistring; end;
 f:array[0..500]of record x,y:longint; str:ansistring; end;
 vb:array[0..21,0..21,1..4]of boolean;
 vp:array[0..21,0..21]of boolean;
 l,r,sx,sy,bx,by,tx,ty,i,j,n,m,t:longint;
 target:boolean;
 s:ansistring;

procedure scanf;
 begin
  fillchar(a,sizeof(a),0);
  for i:=1 to n do
   begin
    for j:=1 to m do
     begin
      read(a[i,j]);
      if a[i,j]='S' then begin a[i,j]:='.'; sx:=i; sy:=j; end;
      if a[i,j]='B' then begin a[i,j]:='.'; bx:=i; by:=j; end;
      if a[i,j]='T' then begin a[i,j]:='.'; tx:=i; ty:=j; end;
     end;
    readln;
   end;
 end;

function bfsman(x,y:integer):boolean;
 var
  ll,rr,i,nx,ny:longint;
 begin
  fillchar(vp,sizeof(vp),0);
  ll:=1; rr:=1;
  f[1].x:=q[l].px; f[1].y:=q[l].py; vp[q[l].px,q[l].py]:=true;
  if (q[l].px=x)and(q[l].py=y) then begin s:=''; exit(true); end;
  while ll<=rr do
   begin
    for i:=1 to 4 do
     begin
      nx:=f[ll].x+dx[i];
      ny:=f[ll].y+dy[i];
      if not vp[nx,ny] and(a[nx,ny]='.')and((nx<>q[l].x)or(ny<>q[l].y)) then
       begin
        vp[nx,ny]:=true;
        inc(rr);
        f[rr].x:=nx;
        f[rr].y:=ny;
        f[rr].str:=f[ll].str+dir[i];
        if (nx=x)and(ny=y) then begin s:=f[rr].str; exit(true); end;
       end;
     end;
    inc(ll);
   end;
  exit(false);
 end;

procedure push(x,y:integer; ch:char; s:ansistring; dire:integer);
 begin
  inc(r);
  vb[x,y,dire]:=true;
  q[r].x:=x; q[r].y:=y;
  q[r].px:=q[l].x; q[r].py:=q[l].y;
  q[r].str:=s+ch;
  q[r].last:=l;
  if (x=tx)and(y=ty) then begin target:=true; exit; end;
 end;

procedure bfsbox;
 begin
  fillchar(vb,sizeof(vb),0);
  target:=false;
  l:=1; r:=1;
  q[1].x:=bx; q[1].y:=by;
  q[1].px:=sx; q[1].py:=sy;
  for i:=1 to 4 do vb[bx,by,i]:=true;
  while l<=r do
   begin
    if (a[q[l].x-1,q[l].y]='.')and(a[q[l].x+1,q[l].y]='.') then
     begin
      if not vb[q[l].x-1,q[l].y,1] and bfsman(q[l].x+1,q[l].y) then push(q[l].x-1,q[l].y,'N',s,1);
      if target then exit;
      if not vb[q[l].x+1,q[l].y,2] and bfsman(q[l].x-1,q[l].y) then push(q[l].x+1,q[l].y,'S',s,2);
      if target then exit;
     end;
    if (a[q[l].x,q[l].y-1]='.')and(a[q[l].x,q[l].y+1]='.') then
     begin
      if not vb[q[l].x,q[l].y-1,3] and bfsman(q[l].x,q[l].y+1) then push(q[l].x,q[l].y-1,'W',s,3);
      if target then exit;
      if not vb[q[l].x,q[l].y+1,4] and bfsman(q[l].x,q[l].y-1) then push(q[l].x,q[l].y+1,'E',s,4);
      if target then exit;
     end;
    inc(l);
   end;
 end;

procedure print(p:longint);
 begin
  if q[p].last<>0 then print(q[p].last);
  write(q[p].str);
  if p=r then writeln;
 end;

begin
 repeat
  inc(t);
  readln(n,m);
  if (n=0)and(m=0) then break;
  scanf;
  bfsbox;
  writeln('Maze #',t);
  if target then print(r) else writeln('Impossible.');
  writeln;
 until false;
end.

š

发表评论

电子邮件地址不会被公开。 必填项已用*标注