题目链接：https://www.acwing.com/problem/content/176/
由于状态数量的限制，我们可以考虑捆绑人与箱子的状态，我们已知每次箱子的移动一定是由人引起的，可以考虑状态是箱子的位置和箱子推动的时候人的方向，用另一个BFS搜索人从当前位置
到达箱子旁边的该方向的位置但是不经过箱子的最短路径。
代码：
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; #define maxn 25 const int inf=0x3f3f3f3f; char s[maxn][maxn]; int r,c; bool vis[maxn][maxn][4];//坐标以及箱子推向的方向 struct node{ int x,y,px,py; string ans;//记录人的移动情况 int step;//箱子移动的步数 }; char a[]={'n','s','w','e'}; char A[]={'N','S','W','E'}; int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; node st,ed; string tmp=""; bool valid(int x,int y){ return x>=1 && x<=r && y>=1 && y<=c && s[x][y]!='#'; } bool bfs2(node& now,int endx,int endy){ tmp=""; queue<node> q; bool v[maxn][maxn]; memset(v,0,sizeof(v)); node c; c.x=now.px; c.y=now.py; c.ans=""; q.push(c); while(!q.empty()){ node cur=q.front(); q.pop(); if(cur.x==endx && cur.y==endy){ tmp=cur.ans; return true; } for(int i=0;i<4;i++){ node nxt=cur; nxt.x=cur.x+dx[i]; nxt.y=cur.y+dy[i]; if(!valid(nxt.x,nxt.y))continue; if(v[nxt.x][nxt.y])continue; if(nxt.x==now.x && nxt.y==now.y)continue;//不经过箱子所在的点 v[nxt.x][nxt.y]=1; nxt.ans=cur.ans+a[i]; q.push(nxt); } } return false;//从now的人的位置没法到达(xx,yy)位置 } string bfs1(){ string ans=""; int cntbox=inf; int cntman=inf; queue<node> q; q.push(st); memset(vis,0,sizeof(vis)); while(!q.empty()){ node now=q.front(); q.pop(); if(now.step > cntbox)return ans; if(s[now.x][now.y]=='T'){ if(now.step < cntbox || (now.step == cntbox && (now.ans.length() < cntman))){ ans=now.ans; cntbox=now.step; cntman=now.ans.length(); } continue;//重新从队列中取node进行扩展 } for(int i=0;i<4;i++){ node nxt=now; nxt.x=now.x+dx[i]; nxt.y=now.y+dy[i]; if(!valid(nxt.x,nxt.y))continue; if(vis[nxt.x][nxt.y][i])continue; int xx=now.x-dx[i]; int yy=now.y-dy[i]; if(!valid(xx,yy))continue; //计算出人从当前位置到推箱子的位置的最短的路径 ,不经过now中的箱子点 if(bfs2(now,xx,yy)){ vis[nxt.x][nxt.y][i]=1; nxt.ans=now.ans+tmp; nxt.ans+=A[i];//箱子的移动 nxt.px=now.x;//当前人的位置 nxt.py=now.y; nxt.step++; q.push(nxt); } } } return ans; } int main(){ int tot=0; // freopen("input.txt","r",stdin); // freoptn("output.txt","w",stdout); while(cin>>r>>c && r && c){ for(int i=1;i<=r;i++)scanf("%s",s[i]+1); for(int i=1;i<=r;i++)//确定初始状态和终止状态 for(int j=1;j<=c;j++){ if(s[i][j]=='B'){ st.x=i,st.y=j; st.ans=""; s[i][j]='.';//图中只有两种位置，易于判断 } if(s[i][j]=='S'){ st.px=i,st.py=j; s[i][j]='.'; } } st.step=0; string ret=bfs1(); if(ret!="")cout<<"Maze "<<"#"<<++tot<<endl<<ret<<endl<<endl; else cout<<"Maze "<<"#"<<++tot<<endl<<"Impossible."<<endl<<endl; } return 0; }