POJ1475 Pushing Boxes 华丽丽的双重BFS

woc累死了写了两个半小时。。。就是BFS？我太菜了。。。

---

刚开始以为让人预先跑一遍BFS，然后一会儿取两节加起来就好了，结果发现求出来的最短路（就是这个意思）会因箱子的移动而变化。。。。我死了QWQ

康康书上正解：双重BFS？！！让人推箱子的时候再跑一遍BFS？！！时间不就爆炸了？！！啊n，m只有20。。。我死。。。

乖乖打正解。。结果又不知道如何传人BFS时的答案。。。想了半天。。就是开一个全局跑完人的BFS直接用就行了。。。

然后BFS跳出的时候还写错了。。否则更新不了

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#define R register int

using namespace std;

const int d[][]={-,,,,,-,,};

char op[]={'n','s','w','e'},OP[]={'N','S','W','E'};

inline int g() {

    R ret=; register char ch; while(!isdigit(ch=getchar()));

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret;

}

int n,m,sx,sy,tx,ty,bx,by;

char mp[][];

bool vis[][],mk[][][];

string ans;

struct node {int x,y,xx,yy; string ans; node() {}

    node(int _x,int _y,int _xx,int _yy,string s):x(_x),y(_y),xx(_xx),yy(_yy),ans(s) {}

}bed,brt;

struct peo {int x,y; string ans; peo() {}

    peo(int _x,int _y,string s):x(_x),y(_y),ans(s) {}

}ped,prt;

inline bool is(char ch) {return ch=='S'||ch=='T'||ch=='B'||ch=='#'||ch=='.';}

inline bool ckpos(int x,int y) {return x<||x>n||y<||y>m;}

bool bfs1(int sx,int sy,int i,int j,int xx,int yy) {

    queue<peo>q;

    if(ckpos(sx,sy)||mp[sx][sy]=='#') return false;

    memset(vis,false,sizeof(vis)); vis[i][j]=true,vis[xx][yy]=true;

    q.push(peo(xx,yy,"")); while(q.size()) {

        prt=q.front(); q.pop();

        if(prt.x==sx&&prt.y==sy) return true;

        for(R i=;i<;++i) {

            R x=prt.x+d[i][],y=prt.y+d[i][]; ped.x=x,ped.y=y;

            if(ckpos(x,y)||vis[x][y]||mp[x][y]=='#') continue; vis[x][y]=true;

            ped.ans=prt.ans+op[i]; q.push(ped);

        }

    } return false;

}

bool bfs() { queue<node>q;

    q.push(node(bx,by,sx,sy,"")); while(q.size()) {

        brt=q.front(); q.pop();

        for(R i=;i<;++i) {

            R x=brt.x+d[i][],y=brt.y+d[i][]; bed.x=x,bed.y=y;

            if(brt.x==tx&&brt.y==ty) return true;

            if(ckpos(x,y)||mk[x][y][i]||mp[x][y]=='#') continue;

            if(bfs1(brt.x-d[i][],brt.y-d[i][],brt.x,brt.y,brt.xx,brt.yy)) {

                bed.xx=brt.x,bed.yy=brt.y,bed.ans=brt.ans+prt.ans+OP[i];

                mk[x][y][i]=true; q.push(bed);

            }

        }

    } return false;

}

signed main() { R t=;

    while(n=g(),m=g(),n!=) {

        memset(mk,false,sizeof(mk));

        for(R i=;i<=n;++i) for(R j=;j<=m;++j) {

            while(!is(mp[i][j]=getchar()));

            if(mp[i][j]=='S') sx=i,sy=j;

            else if(mp[i][j]=='T') tx=i,ty=j;

            else if(mp[i][j]=='B') bx=i,by=j;

        }

        printf("Maze #%d\n",++t);

        if(bfs()) cout<<brt.ans<<'\n';

        else printf("Impossible.\n");

        putchar('\n');

    }

}

---

2019.04.26