| ||||||||||
| 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