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.