POJ 1475 Pushing Boxes

想象您正站在一个二维的迷宫中，迷宫由是正方形的方格组成，这些方格可能被岩石阻塞，也可能没有。您可以向北，南，东或西一步移到下一个方格。这些移动被称为行走（walk）。

在一个空方格中放置了一个箱子，您可以挨着箱子站着，然后按这个方向推动这个箱子，这个箱子就可以被移动到一个临近的位置。这样的一个移动被称为推（push）。除了推以外，箱子不可能用其他的方法被移动，这就意味着如果您把箱子推到一个角落，您就永远不能再把它从角落中推出。

一个空格被标识为目标空格。您的任务就是通过一系列的行走和推把一个箱子推到目标方格中（如图15.4-1）。因为箱子非常重，您希望推的次数最少。您能编写一个程序来给出最佳的序列吗？

双重BFS

每次将箱子移动，然后看人能不能到达箱子移动前，并且与箱子移动方向相反的那个位置。。

说不清楚，就是说假如箱子原来在(x,y),现在箱子在( x+Δx , y+Δy )的位置，那么如果要这样推，人必须能到达( x-Δx , y-Δy )。

所以要记录一下箱子在（Bx,By）的位置时候，人在(x,y)。然后移动之后箱子在(Bx+Δx,By+Δy),并且检验人能不能从(x,y)在不经过(Bx,By)的情况下能否到达(Bx-Δx,By-Δy)。如果可以记录路径然后重复，直到到达目标位置。

因为是广搜，所以在两个BFS中第一个满足条件的状态就是最优状态，重点在判重上。可以用时间戳，并且记录F[BX][BY][X][Y]有没有走过来判重（BX，X都是指的是目标位置，千万不能用有没有经过BX，x来判重，想一想就知道为什么了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using std::string;
using std::queue;
char map[25][25];
struct E{
    int x,y,bx,by,step;
    string Path;
};
int dx[5]={0,1,0,-1};
int dy[5]={1,0,-1,0};
int n,m,V[25][25][25][25];
int cnt,temp[25][25];
int F[25][25][25][25];
char P_M[5]={'e','s','w','n'};
char P_B[5]={'E','S','W','N'};
inline string BFS_M(E now,int sta,int &ok){
    queue<E> q;int GOLX=now.bx-dx[sta],GOLY=now.by-dy[sta];
    string tmp=""; 
    if(F[now.bx][now.by][GOLX][GOLY]){
        ok=0;return tmp;
    }
    F[now.bx][now.by][GOLX][GOLY]=1;
    cnt++;
    if(GOLX<1||GOLY<1||GOLX>n||GOLY>m)  {
        ok=0;
        return tmp;
    }
    while(!q.empty()) q.pop();
    now.Path.clear();
    q.push(now);
    while(!q.empty()){
        E nwe=q.front();q.pop();
        if(nwe.x==GOLX&&nwe.y==GOLY){
            ok=1;
            return nwe.Path;
        }
        for(int i=0;i<=3;++i){
            int gx=nwe.x+dx[i];
            int gy=nwe.y+dy[i];
            if(gx<1||gy<1||gx>n||gy>m) continue;
            if(map[gx][gy]=='#') continue;
            if(gx==now.bx&&gy==now.by) continue;
            if(temp[gx][gy]==cnt) continue;
            temp[gx][gy]=cnt;
            E NWE=nwe;NWE.Path.push_back(P_M[i]);
            NWE.x=gx,NWE.y=gy;
            q.push(NWE);
        }
    }
    ok=0;
    return  tmp;
} 
inline int BFS_B(E S,E T,int &flag){
    queue<E> q;
    while(!q.empty()) q.pop();
    q.push(S);
    while(!q.empty()){
        E now=q.front();q.pop();    
        for(int i=0;i<=3;++i){
            int gx=now.bx+dx[i];
            int gy=now.by+dy[i];
            if(gx<1||gy<1||gx>n||gy>m) continue;
            if(map[gx][gy]=='#') continue;
            int ok=1;
            string  S ;
            S =  BFS_M(now,i,ok);
            if(ok){
                E nwe=now;
                nwe.bx=gx,nwe.by=gy;
                nwe.x=nwe.bx-dx[i],nwe.y=nwe.by-dy[i];
                nwe.Path=nwe.Path+S;
                nwe.Path.push_back(P_B[i]);
                q.push(nwe);
                if(gx==T.x&&gy==T.y){
                    std::cout<<nwe.Path;
                    putchar('\n');
                    flag=1;
                    return 0;
                }
            }
        }
    }
}
int main(){
    E S,T;
    int Case=0;
    while(scanf("%d %d",&n,&m)&&n&&m){
        Case++;
        memset(V,0,sizeof(V));
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                scanf(" %c",&map[i][j]);
                if(map[i][j]=='S')  
                    S.x=i,S.y=j;
                if(map[i][j]=='B')  
                    S.bx=i,S.by=j;
                if(map[i][j]=='T')  T.x=i,T.y=j;
            }
        }
        memset(F,0,sizeof(F));
        memset(V,0,sizeof(V));
        memset(temp,0,sizeof(temp));
        int ok=0;
        printf("Maze #%d\n",Case);
        BFS_B(S,T,ok);
        if(!ok){
            printf("Impossible.\n");
        }
        printf("\n");
    }
    return 0;
}