双重bfs：
在推箱子游戏中人推箱子只有两种情况：
人推箱子：那么箱子此时所处的位置就是人接下来会到达的位置
人找位子推箱子：那么人就要到达箱子下一步到达位子对应的相反方向得那一个格子
所以，主干是箱子的移动过程，箱子每移动一步就对接下来人所处的位子进行考虑。也就是在一次bfs的过程中不断套用另一个bfs
View Code
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <queue> using namespace std; const int maxn = 22; char map[maxn][maxn]; bool visPerson[maxn][maxn]; bool visBox[maxn][maxn]; int R , C; int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; char pushes[4] = { 'E','W','S','N' }; char walks[4] = { 'e','w','s','n' }; string path; struct Node{ int br , bc , pr , pc; string ans; }; bool inMap(int r , int c) { return r>=0 && r<R && c>=0 && c<C; } bool bfs2(int sr, int sc, int er, int ec, int br, int bc, string &ans) { Node node , tmpnode; memset(visPerson,0,sizeof(visPerson)); queue<Node> Q; node.pr = sr; node.pc = sc; node.ans = ""; Q.push(node); visPerson[br][bc] = true; while(!Q.empty()) { node = Q.front(); Q.pop(); if(node.pr == er && node.pc == ec) { ans = node.ans; return true; } if(visPerson[node.pr][node.pc]) continue; visPerson[node.pr][node.pc] = true; for(int i=0;i<4;i++) { int nr = node.pr + dir[i][0]; int nc = node.pc + dir[i][1]; if(inMap(nr,nc) && !visPerson[nr][nc] && map[nr][nc]!='#') { tmpnode.pr = nr; tmpnode.pc = nc; tmpnode.ans =node.ans + walks[i]; Q.push(tmpnode); } } } return false; } bool bfs1(int sr ,int sc, int br, int bc) { Node node , tmpnode; memset(visBox,0,sizeof(visBox)); queue<Node> Q; node.pr = sr; node.pc = sc; node.br = br; node.bc = bc; node.ans = ""; Q.push(node); while(!Q.empty()) { node = Q.front(); Q.pop(); if(visBox[node.br][node.bc]) continue; visBox[node.br][node.bc] = true; if(map[node.br][node.bc]=='T') { path = node.ans; return true; } visBox[node.br][node.bc] = true; for(int i=0;i<4;i++) { int nextr = node.br + dir[i][0]; int nextc = node.bc + dir[i][1]; int backr = node.br - dir[i][0]; int backc = node.bc - dir[i][1]; string ans = ""; if( inMap(nextr,nextc) && inMap(backr,backc) && map[nextr][nextc]!='#' && map[backr][backc]!='#' && !visBox[nextr][nextc] ) { if(bfs2(node.pr, node.pc, backr, backc, node.br, node.bc, ans)) { tmpnode.pr = node.br; tmpnode.pc = node.bc; tmpnode.br = nextr; tmpnode.bc = nextc; tmpnode.ans = node.ans +ans +pushes[i]; Q.push(tmpnode); } } } } return false; } int main() { int cas = 1; int sr , sc , br , bc; while(~scanf("%d%d",&R,&C) && R) { for(int i=0;i<R;i++) scanf("%s",map[i]); for(int i=0;i<R;i++) for(int j=0;j<C;j++) { if(map[i][j]=='S') { sr = i; sc = j; } if(map[i][j]=='B') { br = i; bc = j; } } path = ""; printf("Maze #%d\n",cas++); bfs1(sr,sc,br,bc) ? cout<<path<<endl : cout<<"Impossible."<<endl; cout<<endl; } return 0; }