Imagine you are standing inside a two-dimensional maze composed of square cells which may or may not be filled with rock. You can move north, south, east or west one cell at a step. These moves are called walks.
One of the empty cells contains a box which can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. Such a move is called a push. The box cannot be moved in any other way than by pushing, which means that if you push it into a corner you can never get it out of the corner again.
One of the empty cells is marked as the target cell. Your job is to bring the box to the target cell by a sequence of walks and pushes. As the box is very heavy, you would like to minimize the number of pushes. Can you write a program that will work out the best such sequence?

文章图片

Input
The input contains the descriptions of several mazes. Each maze description starts with a line containing two integers r and c (both <= 20) representing the number of rows and columns of the maze.
Following this are r lines each containing c characters. Each character describes one cell of the maze. A cell full of rock is indicated by a #' and an empty cell is represented by a.’. Your starting position is symbolized by S', the starting position of the box byB’ and the target cell by `T’.
Input is terminated by two zeroes for r and c.
Output
For each maze in the input, first print the number of the maze, as shown in the sample output. Then, if it is impossible to bring the box to the target cell, print “Impossible.”.
Otherwise, output a sequence that minimizes the number of pushes. If there is more than one such sequence, choose the one that minimizes the number of total moves (walks and pushes). If there is still more than one such sequence, any one is acceptable.
Print the sequence as a string of the characters N, S, E, W, n, s, e and w where uppercase letters stand for pushes, lowercase letters stand for walks and the different letters stand for the directions north, south, east and west.
Output a single blank line after each test case.
Sample Input
1 7
SB….T
1 7
SB..#.T
7 11
###########
#T##……#
#.#.#..####
#….B….#
#.######..#
#…..S…#
###########
8 4
….
.##.
.#..
.#..
.#.B
.##S
….
T
0 0
Sample Output
Maze #1
EEEEE
Maze #2
Impossible.
【Pushing Boxes】Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN
Maze #4
swwwnnnnnneeesssSSS
说出来你可能不信，我推了两天的箱子(╥╯^╰╥)
第一次写博客。。。感觉好激动ヽ(￣▽￣)?
看到这道题，诶~~~~，这不就是小时候在老爸手机上玩的推箱子游戏么，那还是个黑白屏幕手机的年代。。。。。(｀?ω?′)
这道题是要我们输出推箱子的最短路径。
我一看题，感觉是这次的题里面最难的，不会啊，这怎么弄。。。然后网上一百度，说什么嵌套的BFS。。。经过这周的学习，我才差不多明白BFS是怎么弄的，而这一下子又来了个嵌套的。。。。。感觉好难。
不过，我觉得，要是这种嵌套的我都能弄出来，那以后理解一层的，应该会容易很多吧￣ω￣=
于是fu~~~
开始吧
这题要先对箱子搜索路径，然后在箱子走的每一步，又对人搜索路径，这样一说的吼~，好像也没什么不好理解的￣▽￣
在我的代码里面，所有后面是 1 的都是关于箱子的，比收入 next1,now1, 2 都是关于人的，而且我的 人的BFS 和 箱子的BFS 都是返回的各自的结构体，到时候好检查内层或外层的路径，看内层或外层的BFS有没有什么出错的地方，两个都没错，再把他们连起来( ? ?ω?? )?
只不过这道题有不少值得思考的细节：
1.人与箱子的连接，也就是内层外层，反正一开始把我搞晕了。。。。可能是变量太多了，有时候眼睛都看花了。
我弄了个图：

文章图片

人要先去看箱子要去的相反方向人能不能去
举个栗子：

文章图片

这样就不能推到终点；
而我返回的都是各自的结构体，所以我就检查人能不能到，如果人不能到，返回的结构体中的坐标会变成(-1,-1);
2.人走的时候，箱子要当作墙
3.箱子走到终点两条路都是一样长时，人要先走短的路
分为：人和箱子同在一行 或 人和箱子同在一列，以及 人和终点在箱子两侧 或 人和终点在箱子同侧；
比如下面两个栗子：

文章图片

此时，箱子走红箭头人走的路最短
附上一组测试数据：
5 10
##########
#T…#…#
#…SB…#
#….#…#
##########
Maze #1
EEseenWWWWWWswN

文章图片

这种情况也是箱子走红箭头最短
另一组测试数据：
11 19
….#####……….
….#…#……….
….#…#……….
..###..B##………
..#……#………
###.#.##.#…######
#…#.##.#####T…#
#……………..#
####..###.#S##….#
…#……#########
…########……..
Maze #2
nwwwnnnwwnneSwswssseeennnWWnwSSSnnwwssseEEEEEEEEEEseNenW
另外就是。。。因为我是一找到目标就返回，所以有时候上次的结果还保存在队列里，所以要及时清除。。。(T ^ T)

#include"iostream" #include"string.h" #include"queue" using namespace std; int N,M; int Sx,Sy/*人的起点*/,Bx,By/*箱子起点*/,Ex,Ey/*箱子终点*/; char Map[22][22]; int BoxVis[22][22][22][22]; /*箱子的标记数组 */ int PeoVis[22][22]; /*人的标记数组 */ int dir[4][2]={-1,0,1,0,0,-1,0,1}; typedef struct PEO { int x,y; string path2; /*用来存内层BFS的路径，阔以检查内层BFS有没有错*/ }Peo; typedef struct BOX { int bx,by; //箱子坐标 int sx,sy; //人的坐标 string path1; char d; string own; /*用来检查外层BFS是否写错。。。 */ }Box; queue q1; queue q2; /*这两个都是用来添加路径的，一个是外层的，一个是内层的*/ char f1(int x,int y) { char d; if(x==-1&&y== 0)d='N'; else if(x== 0&&y==-1)d='W'; else if(x== 1&&y== 0)d='S'; else if(x== 0&&y== 1)d='E'; return d; } char f2(int x,int y) { char d; if(x==-1&&y== 0)d='n'; else if(x== 0&&y==-1)d='w'; else if(x== 1&&y== 0)d='s'; else if(x== 0&&y== 1)d='e'; return d; }/* 这里Sx,Sy是人现在的起点， 看人能不能到ex,ey, 如果不能就返回坐标(-1,-1), BX，BY是箱子现在的坐标 */ Peo PeoBFS(int Sx,int Sy,int ex,int ey,int BX,int BY) { Peo now2,next2; memset(PeoVis,0,sizeof(PeoVis)); while(!q2.empty())q2.pop(); now2.x=Sx; now2.y=Sy; now2.path2=""; PeoVis[Sx][Sy]=1; q2.push(now2); while(!q2.empty()) { now2=q2.front(); q2.pop(); if(now2.x==ex&&now2.y==ey)return now2; { for(int i=0; i<4; i++) { next2.x=now2.x+dir[i][0]; next2.y=now2.y+dir[i][1]; if(next2.x<1||next2.x>N||next2.y<1||next2.y>M)continue; if(Map[next2.x][next2.y]=='#')continue; if(PeoVis[next2.x][next2.y]==0) { next2.path2=now2.path2+f2(dir[i][0],dir[i][1]); PeoVis[next2.x][next2.y]=1; q2.push(next2); } } } } Peo temp2; temp2.x=-1; temp2.y=-1; temp2.path2="不能到"; return temp2; } Box BoxBFS() { Box now1,next1; memset(BoxVis,0,sizeof(BoxVis)); now1.bx=Bx; now1.by=By; now1.sx=Sx; now1.sy=Sy; now1.own=""; now1.path1=""; BoxVis[Bx][By][Sx][Sy]=1; q1.push(now1); while(!q1.empty()) { now1=q1.front(); now1=q1.front(); q1.pop(); if(now1.bx==Ex&&now1.by==Ey)return now1; next1.sx=now1.bx; next1.sy=now1.by; int sum=0; int flag=0; if(now1.bx==now1.sx) { if( (now1.by-Ey)*(now1.by-now1.sy)<0 ) { flag=1; /*左右优先; */ swap(dir[0][0],dir[2][0]); swap(dir[0][1],dir[2][1]); swap(dir[1][0],dir[3][0]); swap(dir[1][1],dir[3][1]); } /*否则上下优先; */ } else if(now1.by==now1.sy) { if( (now1.bx-Ex)*(now1.bx-now1.sx)<0 ); /*上下优先*/ else { flag=1; /*左右优先*/ swap(dir[0][0],dir[2][0]); swap(dir[0][1],dir[2][1]); swap(dir[1][0],dir[3][0]); swap(dir[1][1],dir[3][1]); } } for(int i=0; i<4; i++) {next1.bx=now1.bx+dir[i][0]; next1.by=now1.by+dir[i][1]; if(next1.bx<1||next1.bx>N||next1.by<1||next1.by>M)continue; next1.own=now1.own+f1(dir[i][0],dir[i][1]); next1.path1=now1.path1; if(Map[next1.bx][next1.by]=='#')continue; if(Map[now1.bx-dir[i][0]][now1.by-dir[i][1]]=='#')continue; Map[now1.bx][now1.by]='#'; /*人走的时候，箱子要当作墙*/ Peo ans2=PeoBFS(now1.sx,now1.sy,now1.bx-dir[i][0],now1.by-dir[i][1],now1.bx,now1.by); Map[now1.bx][now1.by]='.'; if(ans2.x!=-1&&ans2.y!=-1) { ans2.path2=ans2.path2+f1(dir[i][0],dir[i][1]); if(BoxVis[next1.bx][next1.by][now1.bx-dir[i][0]][now1.by-dir[i][1]]==0) {BoxVis[next1.bx][next1.by][now1.bx-dir[i][0]][now1.by-dir[i][1]]=1; next1.path1=next1.path1+ans2.path2; q1.push(next1); } } } if(flag==1) { //左右优先换回来; swap(dir[0][0],dir[2][0]); swap(dir[0][1],dir[2][1]); swap(dir[1][0],dir[3][0]); swap(dir[1][1],dir[3][1]); }} Box temp1; temp1.path1="Impossible."; return temp1; } int main() { int t=1; while(cin>>N>>M&&N!=0&&M!=0) {while(!q1.empty())q1.pop(); while(!q2.empty())q2.pop(); memset(Map,0,sizeof(Map)); for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) { cin>>Map[i][j]; if(Map[i][j]=='S') { Sx=i; Sy=j; } if(Map[i][j]=='T') { Ex=i; Ey=j; } if(Map[i][j]=='B') { Bx=i; By=j; } } cout<<"Maze #"<