AcWing174 推箱子
这个小人，不讲武德，总是围着箱子绕一圈再推。。然后因为这个调了三四个小时。。
双 BFS。搜索状态表示为 ((x,y,d))，表示箱子坐标是 ((x,y))，小人在箱子的 (d) 方向。外面的 BFS 算箱子路径，里面的 BFS 算小人路径。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<string>
using namespace std;
const int N=20;
const char dir[4]={'n','s','w','e'},Dir[4]={'N','S','W','E'};
const int nxt[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char s[N+10][N+10];
int n,m;
bool vis1[N+10][N+10];
struct man
{
int x,y;
string s;
man()
{
x=y=0;
s="";
}
man(int xx,int yy,string ss)
{
x=xx;
y=yy;
s=ss;
}
};
// (box_x, box_y) can't visit
string expand(int bx,int by,int stx,int sty,int edx,int edy)
{
if(stx==edx && sty==edy) return "";
memset(vis1,false,sizeof(vis1));
queue<man> que;
vis1[bx][by]=1;
vis1[stx][sty]=1;
que.push(man(stx,sty,""));
while(!que.empty())
{
man head=que.front();
que.pop();
if(head.x==edx && head.y==edy) return head.s;
for(int i=0;i<4;i++)
{
int xx=head.x+nxt[i][0],yy=head.y+nxt[i][1];
if(xx<1 || xx>n || yy<1 || yy>m) continue;
if(s[xx][yy]=='#' || vis1[xx][yy]) continue;
vis1[xx][yy]=1;
que.push(man(xx,yy,head.s+dir[i]));
}
}
return "Fail";
}
int stx,sty,edx,edy,px,py;
struct box
{
int x,y,dir,len;
string s;
box()
{
len=0;
x=y;
dir=-1;
s="";
}
box(int xx,int yy,int ddir,string ss,int llen)
{
len=llen;
x=xx;
y=yy;
dir=ddir;
s=ss;
}
};
int f_box[N+10][N+10][4],f_man[N+10][N+10][4];
string bfs()
{
memset(f_box,0x3f,sizeof(f_box));
memset(f_man,0x3f,sizeof(f_man));
queue<box> que;
for(int i=0;i<4;i++)
{
int xx=stx-nxt[i][0],yy=sty-nxt[i][1];
string tmp=expand(stx,sty,px,py,xx,yy);
if(tmp[0]=='F') continue;
que.push(box(stx,sty,i,tmp,0));
f_box[stx][sty][i]=0;
f_man[stx][sty][i]=min(f_man[stx][sty][i],(int)tmp.length());
}
int l=0x7fffffff,l1=0x7fffffff;
string ans="Impossible.";
while(!que.empty())
{
box head=que.front();
que.pop();
if(head.x==edx && head.y==edy)
{
if(head.len<l)
{
l=head.len;
ans=head.s;
l1=head.s.length();
}
else if(head.len==l)
{
if((int)head.s.length()<l1)
{
l1=(int)head.s.length();
ans=head.s;
}
}
continue;
}
for(int i=0;i<4;i++)
{
int xx=head.x+nxt[i][0],yy=head.y+nxt[i][1];
if(xx<1 || xx>n || yy<1 || yy>m) continue;
if(s[xx][yy]=='#') continue;
string tmp=
expand(head.x,head.y,head.x-nxt[head.dir][0],
head.y-nxt[head.dir][1],head.x-nxt[i][0],
head.y-nxt[i][1]);
if(tmp[0]=='F') continue;
if(head.len+1>f_box[xx][yy][i]) continue;
if(head.len+1==f_box[xx][yy][i])
{
string tmp1=head.s+tmp+Dir[i];
if((int)tmp.length()>f_man[xx][yy][i]) continue;
else f_man[xx][yy][i]=min(f_man[xx][yy][i],(int)tmp.length());
}
else
{
string tmp1=head.s+tmp+Dir[i];
f_box[xx][yy][i]=head.len+1;
f_man[xx][yy][i]=(int)tmp1.length();
}
que.push(box(xx,yy,i,head.s+tmp+Dir[i],head.len+1));
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
int Case=0;
while(1)
{
cin>>n>>m;
if(n==0 && m==0) break;
for(int i=1;i<=n;i++) cin>>(s[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='B')
{
stx=i;
sty=j;
}
else if(s[i][j]=='S')
{
px=i;
py=j;
}
else if(s[i][j]=='T')
{
edx=i;
edy=j;
}
}
}
cout<<"Maze #"<<++Case<<endl<<bfs()<<endl<<endl;
}
return 0;
}