zoj 1249 Pushing Boxes

zoj 1249 Pushing Boxes

#include<iostream>#include<vector>#include<cstdio>#include<string>#include<queue>#include<cstring>using namespace std;int n,m;char map[25][25];int       dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};int other_dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};int ex,ey,flag;bool vis[25][25][25][25];bool mark[25][25];char op[]="nswe";char big_op[]="NSWE";string ans;struct node{    int b_x,b_y;    int p_x,p_y;    int step;    string ans;}s_pos;bool cheack(int x,int y){     return x>=0&&x<n&&y>=0&&y<m&&map[x][y]!='#';     return false;}bool people_cango(node &cur,node last,int e_x,int e_y){     queue<node > q;  node per;per=cur;   per.step=0;  per.ans="";     memset(mark,false,sizeof(mark));     q.push(per);     mark[cur.p_x][cur.p_y]=true;     while(!q.empty()){         node now=q.front();  q.pop();          if(now.p_x==e_x&&now.p_y==e_y){  cur.ans+=now.ans;  return true;}         for(int i=0;i<4;i++){  node next=now;     next.step+=1;  next.p_x+=dir[i][0];   next.p_y+=dir[i][1];  if(cheack(next.p_x,next.p_y)&&!mark[next.p_x][next.p_y]){      if(next.p_x==last.b_x&&next.p_y==last.b_y)  continue;  //遇见箱子      mark[next.p_x][next.p_y]=true;      next.ans+=op[i];      if(next.p_x==e_x&&next.p_y==e_y){         cur.ans+=next.ans;         return true;      }      q.push(next);  }         }     }    return false;}void bfs(){     queue<node > q;     memset(vis,false,sizeof(vis));     q.push(s_pos);     vis[s_pos.b_x][s_pos.b_y][s_pos.p_x][s_pos.p_y]=true;     while(!q.empty()){         node now = q.front(); q.pop();         for(int i=0;i<4;i++){  node next = now;   next.step+=1;  next.b_x+=dir[i][0];  next.b_y+=dir[i][1];  int x=now.b_x+other_dir[i][0];         int y=now.b_y+other_dir[i][1];  if(cheack(next.b_x,next.b_y)&&cheack(x,y)&&!vis[next.b_x][next.b_y]     [now.b_x][now.b_y]){      if(people_cango(next,now,x,y)){         next.p_x=now.b_x;         next.p_y=now.b_y;         next.ans+=big_op[i];          if(next.b_x==ex&&next.b_y==ey){  flag=1;  ans=next.ans;  return ;         }         vis[next.b_x][next.b_y][next.p_x][next.p_y]=true;         q.push(next);      }  }         }     }}int main(){    int ca=1;    while(scanf("%d%d",&n,&m)!=EOF,n+m){          for(int i=0;i<n;i++)  scanf("%s",map[i]);          for(int i=0;i<n;i++){   for(int j=0;j<m;j++){   if(map[i][j]=='T'){       ex=i,ey=j;   }   if(map[i][j]=='B'){       s_pos.b_x=i;  s_pos.b_y=j;   }   if(map[i][j]=='S'){       s_pos.p_x=i;  s_pos.p_y=j;   }   }          }          flag=0; s_pos.step=0;  s_pos.ans="";          bfs();          cout<<"Maze #"<<ca++<<endl;          if(flag){  cout<<ans<<endl;          }          else          cout<<"Impossible."<<endl;          cout<<endl;    }    return 0;}