#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <string>
using namespace std;
char m[20][20];
int f[20][20][20][20][2];
int startx,starty,targetx,targety,bx,by;
int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char step[4]={'n','s','w','e'};
struct Node{
   string way;
   int x[2],y[2];
   int push,walk;
};
int r,c;    
void bfs(){
   bool yes=false;
   string best;
   int bw=0,bp=0,x,y,i,t,x1,x2,y1,y2,push,walk;
   memset(f,-1,sizeof(f));
   queue<Node> q;
   Node temp,now;
   temp.way="";
   temp.x[0]=startx;  temp.y[0]=starty;
   temp.x[1]=bx;  temp.y[1]=by;
   temp.push=0;  temp.walk=0;
   f[startx][starty][bx][by][0]=0;
   f[startx][starty][bx][by][1]=0;
   while(!q.empty())  q.pop();
   q.push(temp);
   while(!q.empty()){
      now=q.front();
      q.pop(); 
      x1=now.x[0];
      y1=now.y[0];
      x2=now.x[1];
      y2=now.y[1];
      push=now.push;
      walk=now.walk;
      //cout<<now.way<<' '<<now.x[0]<<' '<<now.y[0]<<' '<<now.x[1]<<' '<<now.y[1]<<endl;
      //getch();
      if(x2==targetx&&y2==targety){
         if(!yes){
            best=now.way;
            yes=true;
            bw=walk;
            bp=push;    
         }      
         else{
            if(bp>push||(bp==push&&bw>walk)){
               best=now.way;
               bp=push;
               bw=walk;
            }    
         }    
         continue;
      }    
      t=x1+y1-x2-y2;
      if(t==1||t==-1){
         x=2*x2-x1;
         y=2*y2-y1;  //推箱子 
         if(x>=0&&x<r&&y>=0&&y<c&&m[x][y]=='.'){
            if(f[x2][y2][x][y][0]==-1||
               f[x2][y2][x][y][0]>(push+1)||
               (f[x2][y2][x][y][0]==(push+1)&&f[x2][y2][x][y][1]>walk)){
               //cout<<"push ";
               temp=now;
               if(x>x2)  temp.way+='S';
               else if(x<x2)  temp.way+='N';
               else if(y>y2)  temp.way+='E';
               else if(y<y2)  temp.way+='W';
               temp.x[0]=x2;
               temp.y[0]=y2;
               temp.x[1]=x;
               temp.y[1]=y; 
               temp.push=f[x2][y2][x][y][0]=push+1;
               f[x2][y2][x][y][1]=walk;
               //cout<<temp.way<<' '<<temp.x[0]<<' '<<temp.y[0]<<' '<<temp.x[1]<<' '<<temp.y[1]<<endl;
               q.push(temp);
            }     
         }    
      }
      for(i=0;i<4;i++){
         x=x1+move[i][0];
         y=y1+move[i][1];
         if(x>=0&&x<r&&y>=0&&y<c&&(x!=x2||y!=y2)&&m[x][y]=='.'){
            if(f[x][y][x2][y2][0]==-1||
               f[x][y][x2][y2][0]>push||
               (f[x][y][x2][y2][0]==push&&f[x][y][x2][y2][1]>walk+1)){
               //cout<<"walk ";
               temp=now;
               temp.way+=step[i];
               temp.x[0]=x;
               temp.y[0]=y;
               f[x][y][x2][y2][0]=push;
               temp.walk=f[x][y][x2][y2][1]=now.walk+1;
               //cout<<temp.way<<' '<<temp.x[0]<<' '<<temp.y[0]<<' '<<temp.x[1]<<' '<<temp.y[1]<<endl;
               q.push(temp);
            }    
         }    
      }       //走路     
   }    
   if(yes)  cout<<best<<endl;
   else  cout<<"Impossible."<<endl;
   return ;
}    
int main(){
   int k=1,i,j;
   char blank;
   while(cin>>r>>c&&(r||c)){
      for(i=0;i<r;i++){
         for(j=0;j<c;j++){
            //scanf("%c",&m[i][j]);
            cin>>m[i][j];
            if(m[i][j]=='S')  { startx=i;  starty=j; m[i][j]='.'; }
            else if(m[i][j]=='T')  { targetx=i;  targety=j;  m[i][j]='.'; }
            else if(m[i][j]=='B')  { bx=i;  by=j;  m[i][j]='.'; }
         }    
         //scanf("%c",&blank);
      }     
      /*for(i=0;i<r;i++){
         for(j=0;j<c;j++)  cout<<m[i][j];
         cout<<endl;
      }*/  
      printf("Maze #%d\n",k++);
      bfs();
      printf("\n");
   }    
   return 0;
}    

• Re:怎么没有人理我？自己顶！.. (0) yzg_1984 2005-05-10 22:15:52
  • Re:怎么没有人理我？自己顶！.. (4) yzg_1984 2005-05-11 12:07:48
    • 自己查吧，so难的题，估计不会有人看的~_~ (8) c0500301036 2005-05-11 13:02:44
      • Re:自己查吧，so难的题，估计不会有人看的~_~ (16) yzg_1984 2005-05-12 13:09:23
        • cong~~ (20) c0500301036 2005-05-12 13:17:14