Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
感觉写这种题是要折寿的#include<iostream> #include<algorithm> #include<string.h> #include<string> #include<cstdio> #include<queue> #include<stack> using namespace std; char graph[30][30]; int n,m; struct node { int step_B,step_S,sx,sy,bx,by; }; node flag[30][30][30][30]; node temp,temp_1; struct coor { int x,y; }; coor S,B,T; void init() { for(int i=0; i<n; ++i) { for(int j=0; j<m; ++j) { cin>>graph[i][j]; if(graph[i][j]=='S') { S.x=i; S.y=j; } else if(graph[i][j]=='B') { B.x=i; B.y=j; } else if(graph[i][j]=='T') { T.x=i; T.y=j; } } } for(int sx=0; sx<n; ++sx) { for(int sy=0; sy<m; ++sy) { for(int bx=0; bx<n; ++bx) { for(int by=0; by<m; ++by) { flag[sx][sy][bx][by].step_B=-1; flag[sx][sy][bx][by].step_S=-1; } } } } } int dx[4]= {0,0,1,-1}; int dy[4]= {1,-1,0,0}; void bfs() { queue<node>Q; flag[S.x][S.y][B.x][B.y].step_B=0; flag[S.x][S.y][B.x][B.y].step_S=0; flag[S.x][S.y][B.x][B.y].sx=-1; flag[S.x][S.y][B.x][B.y].sy=-1; flag[S.x][S.y][B.x][B.y].bx=-1; flag[S.x][S.y][B.x][B.y].by=-1; temp.step_S=0; temp.step_B=0; temp.sx=S.x; temp.sy=S.y; temp.bx=B.x; temp.by=B.y; Q.push(temp); while(!Q.empty()) { temp=Q.front(); // printf("%d %d %d %d \n",temp.sx,temp.sy,temp.bx,temp.by); Q.pop(); for(int i=0; i<4; ++i) { temp_1=temp; temp_1.step_S=temp.step_S+1; temp_1.sx=temp_1.sx+dx[i]; temp_1.sy=temp_1.sy+dy[i]; if(temp_1.sx==temp_1.bx&&temp_1.sy==temp_1.by) { temp_1.bx=temp_1.bx+dx[i]; temp_1.by=temp_1.by+dy[i]; temp_1.step_B=temp_1.step_B+1; } if(graph[temp_1.sx][temp_1.sy]=='#'||graph[temp_1.bx][temp_1.by]=='#'||temp_1.sx<0||temp_1.sx>=n||temp_1.bx<0||temp_1.bx>=n|| temp_1.sy<0||temp_1.sy>=m||temp_1.by<0||temp_1.by>=m) { continue; } if(flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_S==-1||flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_S>temp.step_S+1) { if(flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B==-1||flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B>=temp.step_B+1) { flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by]=temp; flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_S=temp.step_S+1; flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B=temp.step_B+1; Q.push(temp_1); } } if(flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B>temp.step_B+1) { flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by]=temp; flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_S=temp.step_S+1; flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B=temp.step_B+1; Q.push(temp_1); } } } } int main() { ios::sync_with_stdio(false); int ctor=1; while(cin>>n>>m) { if(n+m==0) break; init(); cout<<"Maze #"<<ctor++<<endl; // cout<<"*************"<<endl; bfs(); int SX,SY,BX,BY,ans_B=100000,ans_S=100000; for(int sx=0; sx<n; ++sx) { for(int sy=0; sy<m; ++sy) { if(flag[sx][sy][T.x][T.y].step_B!=-1&&flag[sx][sy][T.x][T.y].step_S!=-1) if(flag[sx][sy][T.x][T.y].step_B<ans_B||(flag[sx][sy][T.x][T.y].step_B==ans_B&&flag[sx][sy][T.x][T.y].step_S<ans_S)) { ans_B=flag[sx][sy][T.x][T.y].step_B; ans_S=flag[sx][sy][T.x][T.y].step_S; // cout<<ans_B<<endl; SX=sx; SY=sy; BX=T.x; BY=T.y; } } } if(ans_B==100000) { cout<<"Impossible."<<endl; } else { stack<node>SS; temp.sx=SX; temp.sy=SY; temp.bx=BX; temp.by=BY; while(flag[temp.sx][temp.sy][temp.bx][temp.by].step_S>0) { SS.push(temp); temp=flag[temp.sx][temp.sy][temp.bx][temp.by]; } // cout<<flag[temp.sx][temp.sy][temp.bx][temp.by].step_S<<endl; temp.sx=S.x; temp.sy=S.y; temp.bx=B.x; temp.by=B.y; while(!SS.empty()) { temp_1=SS.top(); SS.pop(); char c; int x,y; x=temp_1.sx-temp.sx; y=temp_1.sy-temp.sy; if(x==0&&y==1) c='e'; else if(x==0&&y==-1) c='w'; else if(x==1&&y==0) c='s'; else if(x==-1&&y==0) c='n'; if(temp_1.bx!=temp.bx||temp_1.by!=temp.by) c=c-32; cout<<c; // printf("(%d,%d)->(%d,%d) :%c\n",temp.sx,temp.sy,temp_1.sx,temp_1.sy,c); temp=temp_1; } cout<<endl; } cout<<endl; //printf("Ans= %d\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator