想象您正站在一个二维的迷宫中,迷宫由是正方形的方格组成,这些方格可能被岩石阻塞,也可能没有。您可以向北,南,东或西一步移到下一个方格。这些移动被称为行走(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;
}
0 条评论