题解 UVA589 【Pushing Boxes】

``` 20191013修改：个人博客网址变更 ``` **欢迎前往[我的博客查看](https://officerbonin.home.blog/2019/07/16/uva589/)** 本题拿到来看，首先dfs在20*20的情况下是非常吃紧的，况且我们有两个移动物体：人与箱子。 所以首先先否定DFS（A*说不定行但反正我写不出来） 随后，这种走迷宫问题往BFS想。 仅仅是箱子移动，写BFS没有什么难度，于是要考虑人。 人推，推箱子，那么人必须得到**推的方向对面**，也就是我把**箱子往上推**，**人**得**在下面**。那么把人去推箱子要过去的位置暂时**称为人的目标位置**。 所以，如果推箱子到tarboxx,tarboxy，nx、ny为方向数组，人的目标位置就可以这么表示： ``` tarboxx=boxnowx+nx[i]; tarboxy=boxnowy+ny[i]; tarmanx=boxnowx+(-nx[i]); tarmany=boxnowy+(-ny[i]); ``` 所以我们还算**人过不过得去、人怎么过去**。这个时候只有再套一个BFS。专门计算人的路径。 这道题就简单明了了： 第一个（外层BFS）每到一个状态，对**四个方向移动**都进行枚举和判断（人能否走过去）。 此外，算人到目标位置的BFS应该判重。 **推箱子的BFS也应该判重**，定义vis[x][y][i]=1为：箱子**从i方向**去过（x,y)的位置。为啥这么定义呢？想想，箱子**并不是不能走重复路径**，而且**有时候必须走重复路径**，但是**没有必要来回三趟**或以上。 下面参考代码，~~有点长~~但是~~我认为比较好懂~~ 注意**多组数据的初始化**，还有**不加vis超时**。。。 ```cpp using namespace std; int n,m; struct node { int nowboxx,nowboxy; int nowmanx,nowmany; string ans; }; struct node2 { int xx, yy; string ways; }; bool isw[25][25]; int nx[6]= {0,-1,1,0,0}; int ny[6]= {0,0,0,-1,1}; int wayofvis[25][25][5]; char waysignz[6]=" nswe"; char waysignt[6]=" NSWE"; bool fpan; int mapf[25][25]; inline string bfspan(int nowboxx,int nowboxy,int stxx,int styy,int enxx,int enyy) { queue<node2>bfsq2; node2 p; memset(isw,0,sizeof isw); bfsq2.push({stxx,styy,""}); isw[stxx][styy]=1; int nowx,nowy,tarx,tary,nowcnt; string waynow; while(!bfsq2.empty()) { p=bfsq2.front(),bfsq2.pop(); nowx=p.xx,nowy=p.yy,waynow=p.ways; if(nowx==enxx&&nowy==enyy) { fpan=1; return waynow; } for(int i = 1; i <= 4; i++) { tarx=nowx+nx[i],tary=nowy+ny[i]; if(!mapf[tarx][tary]||isw[tarx][tary]||tarx==nowboxx&&tary==nowboxy|| (tarx>n||tarx<1||tary>m||tary<1) ) continue; isw[tarx][tary]=1; bfsq2.push({tarx,tary,waynow+waysignz[i]}); } } fpan=0; return ""; } int stboxx,stboxy,stmanx,stmany,enx,eny; string ans,anspr; void bfs() { queue<node>bfsq; node p; bfsq.push({stboxx,stboxy,stmanx,stmany,""}); int boxnowx,boxnowy,mannowx,mannowy; int tarboxx,tarboxy,tarmanx,tarmany; int nowcnt,nowmanride; string ansp; char way; while(!bfsq.empty()) { p=bfsq.front(); bfsq.pop(); boxnowx=p.nowboxx,boxnowy=p.nowboxy; mannowx=p.nowmanx,mannowy=p.nowmany; ansp=p.ans; if(boxnowx==enx&&boxnowy==eny) { printf("%s\n",ansp.c_str()); return; } for(int i = 1; i <= 4; i++) { tarboxx=boxnowx+nx[i]; tarboxy=boxnowy+ny[i]; if(!mapf[tarboxx][tarboxy]) continue; tarmanx=boxnowx+(-nx[i]); tarmany=boxnowy+(-ny[i]); if(!mapf[tarmanx][tarmany]||tarmanx>n||tarmanx<1||tarmany>m||tarmany<1||tarboxx>n||tarboxx<1||tarboxy>m||tarboxy<1) continue; if(mannowx==tarmanx&&mannowy==tarmany&&!wayofvis[tarboxx][tarboxy][i]) { bfsq.push({tarboxx,tarboxy,boxnowx,boxnowy,ansp+waysignt[i]}); wayofvis[tarboxx][tarboxy][i]=1; } else { anspr=bfspan(boxnowx,boxnowy,mannowx,mannowy,tarmanx,tarmany); if(fpan&&!wayofvis[tarboxx][tarboxy][i]) { bfsq.push({tarboxx,tarboxy,boxnowx,boxnowy,ansp+anspr+waysignt[i]}); wayofvis[tarboxx][tarboxy][i]=1; } } } } printf("Impossible.\n"); } int main() { while(~scanf("%d%d",&n,&m)&&(n+m)) { memset(wayofvis,0,sizeof wayofvis); char x; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin>>x; if(x=='#') mapf[i][j]=0; else mapf[i][j]=1; if(x=='B') stboxx=i,stboxy=j; else if(x=='S') stmanx=i,stmany=j; else if(x=='T') enx=i,eny=j; } } bfs(); } } ```