Description：

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 by `B' 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.

Maze #3

eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4

swwwnnnnnneeesssSSS

解题思路：

就是一个推箱子的游戏，问你人是否能够把箱子推到对应的终点位置，这个题需要双BFS，一个用来记录箱子，一个用来记录人，但是需要注意的是要先记录箱子的BFS，在搜索箱子的过程中再进行人的BFS，具体的我们看代码吧，注释写的也挺详细的！！！

程序代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 50
struct status//对应箱子 
{
  int person_x,person_y;
  int box_x,box_y;
  string ans;//利用C++，STL里的string拼接字符串来记录路径 
}p,q;
struct node//对应人 
{
  int x,y;
  string ans;
}P,Q;
int dx[]={-1,1,0,0};//方向数组 
int dy[]={0,0,1,-1};
char pm[]={'n','s','e','w'};//位置数组，小写代表人的移动 
char pb[]={'N','S','E','W'};//大写代表箱子的移动 
int visp[MAXN][MAXN],visb[MAXN][MAXN];
char G[MAXN][MAXN];
int sx,sy,ex,ey,bx,by,r,c;
int judge(int x,int y)
{
  if(x>=0&&x<r&&y>=0&&y<c)//没有越界 
    return true;
  return false;
}
int bfs2(int start_x,int start_y,int end_x,int end_y)
{
  memset(visp,0,sizeof(visp));//清零人的标记数组 
  P.x=start_x;//人的初始位置坐标 
  P.y=start_y;
  P.ans="";//记录路径 
  visp[P.x][P.y]=1;//标记此点 
  visp[p.box_x][p.box_y]=1;//箱子的起始坐标人无法到达，相当于障碍 
  queue<node> qq;
  qq.push(P);//入队
  while(!qq.empty())//队列不为空 
  {
    P=qq.front();//取队首 
    qq.pop();//弹出队首 
    if(P.x==end_x&&P.y==end_y)//到达可以推箱子的位置坐标 
      return 1;
    for(int i=0;i<4;i++)
    {
      int xx=P.x+dx[i];//人移动之后的位置坐标 
      int yy=P.y+dy[i];
      if(judge(xx,yy)&&G[xx][yy]!='#'&&!visp[xx][yy])//判断 
      {
        visp[xx][yy]=1;//标记此点 
        Q.x=xx;//更新人的位置坐标
        Q.y=yy;
        Q.ans=P.ans+pm[i];//记录路径 
        qq.push(Q);//新的点入队 
      }
    }
  }
  return 0;
}
int bfs1()
{
  memset(visb,0,sizeof(visb));//清零箱子的标记数组 
  p.person_x=sx;//人的初始位置坐标 
  p.person_y=sy;
  p.box_x=bx;//箱子的初始位置坐标 
  p.box_y=by;
  p.ans="";//记录路径 
  visb[bx][by]=1;//标记 
  queue<status> st; 
  st.push(p);//入队 
  while(!st.empty())//队列不为空 
  {
    p=st.front();//取队首 
    st.pop();//弹出队首 
    for(int i=0;i<4;i++)
    {
      int nx=p.box_x+dx[i];//箱子移动之后的位置坐标 
      int ny=p.box_y+dy[i];
      int tx=p.box_x-dx[i];//人到达可以推箱子的位置坐标 
      int ty=p.box_y-dy[i];
      if(judge(nx,ny)&&G[nx][ny]!='#'&&judge(tx,ty)&&G[tx][ty]!='#'&&!visb[nx][ny])//判断 
      {
        if(bfs2(p.person_x,p.person_y,tx,ty))//将人的起始位置和能推箱子的位置带入进行人的bfs 
        {
          visb[nx][ny]=1;//标记 
          q.box_x=nx;//更新箱子坐标 
          q.box_y=ny;
          q.person_x=p.box_x;//箱子的上一位置坐标就是人此时的位置坐标 
          q.person_y=p.box_y;
          q.ans=p.ans+P.ans+pb[i];//记录路径 
          if(nx==ex&&ny==ey)//到达终点 
            return 1;
          st.push(q);//新的信息带入队列 
        }
      }
    }
  }
  return 0;
}
int main()
{
  int ans=1;
  while(~scanf("%d %d",&r,&c))
  {
    if(r==0&&c==0)
      break;
    for(int i=0;i<r;i++)
    {
      scanf("%s",G[i]);
      for(int j=0;j<c;j++)
      {
        if(G[i][j]=='S')//人起始的位置 
        {
          sx=i;
          sy=j;
        }
        if(G[i][j]=='B')//箱子起始的位置 
        {
          bx=i;
          by=j;
        }
        if(G[i][j]=='T')//箱子的终点位置 
        {
          ex=i;
          ey=j;
        }
      }
    }
    printf("Maze #%d\n",ans++);
    if(bfs1())//先进行箱子的bfs 
      printf("%s\n",q.ans.c_str());//返回一个指向正规C字符串的指针
    else//箱子无法推到终点 
      printf("Impossible.\n");
    printf("\n");
  }
  return 0;
}