| ||||||||||
| 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 | |||||||||
给点数据啊 我wa疯了# include <iostream>
# define check(xx,yy) (xx>0&&yy>0&&xx<=m&&yy<=n)
using namespace std;
const int MAXN=21;
const int move[][2]={{-1,0},{1,0},{0,-1},{0,1}}; //N S W E
const char M[5]="NSWE";
int op[4][4];
char mate[MAXN][MAXN];
int m,n;
int bx,by , tax,tay , rx,ry; //the init of box ,ren and Target
int ansb[10000][3], ansr[10000], ans[10000];
bool vb[MAXN][MAXN] , vr[MAXN][MAXN];
struct queue{
int pre; //qian
char rx,ry;
char x,y;
}qu[10000000];
int qr[1000000][3]; //0,1-x,y 2-pre
int bfsr(int rrx,int rry,int edx,int edy)
{
if(!(check(edx,edy))) return -1;
int e=1,h=0,i,tx,ty;
memset(vr,0,sizeof(vr));
qr[e][0]=rrx,qr[e][1]=rry;
qr[e][2]=-1;
while(e-h)
{
h++;
for(i=0;i<4;i++)
{
tx=qr[h][0]+move[i][0],ty=qr[h][1]+move[i][1];
if(check(tx,ty) && !vr[tx][ty] && mate[tx][ty]!='#') //r exp_node
{
++e;
qr[e][0]=tx,qr[e][1]=ty;
qr[e][2]=h;
vr[tx][ty]=1;
if(tx==edx && ty==edy) return e;
}
}
}
return -1;
}
int bfs()
{
int e=1,h=0,i,tx,ty,a,ex,ey;
qu[e].pre=-1;
qu[e].rx=rx,qu[e].ry=ry;
qu[e].x =bx,qu[e].y =by;
memset(vb,false,sizeof(vb));
vb[bx][by]=true;
while(e-h)
{
h++;
for(i=0;i<4;i++)
{
tx=qu[h].x+move[i][0],ty=qu[h].y+move[i][1];
if(check(tx,ty) && !vb[tx][ty] && mate[tx][ty]!='#')
{
ex=qu[h].x-move[i][0],ey=qu[h].y-move[i][1];
a=1;
mate[ qu[h].x ][ qu[h].y ]='#';
if(!(qu[h].rx==ex && qu[h].ry==ey)) a=bfsr(qu[h].rx,qu[h].ry,ex,ey);
mate[ qu[h].x ][ qu[h].y ]='.';
if(a+1) //player can reach than exp_node
{
++e;
qu[e].pre=h,qu[e].x=tx,qu[e].y=ty;
qu[e].rx=qu[h].x,qu[e].ry=qu[h].ry;
vb[tx][ty]=1;
if(tx==tax&&ty==tay) return e;
}
}
}
}
return -1;
}
void solve()
{
int i,j,a,k,kk,ak=0,ex,ey,t;
memset(mate,0,sizeof(mate));
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
cin>>mate[i][j];
switch(mate[i][j])
{
case 'B': bx=i,by=j;break;
case 'T': tax=i,tay=j;break;
case 'S': rx=i,ry=j;break;
}
}
}
k=0;
a=bfs();
if(a==-1){puts("Impossible.");return;}
while(qu[a].pre!=-1)
{
t=qu[a].pre;
ansb[++k][0]=op[ qu[a].x - qu[t].x +1 ][ qu[a].y - qu[t].y +1 ];
ansb[k][1]=a,ansb[k][2]=t;
a=t;
}
for(i=k;i>0;i--)
{
mate[qu[ansb[i][2]].x ][qu[ansb[i][2]].y]='#';
ex=qu[ansb[i][2]].x - move[ansb[i][0] ][0],ey=qu[ ansb[i][2] ].y - move[ansb[i][0] ][1];
if(ex==rx&&ey==ry) goto aaa;
a=bfsr( rx,ry,ex , ey);
if(a==-1){puts("Impossible.");return;}
kk=0;
while(qr[a][2]!=-1)
{
t=qr[a][2];
ansr[++kk]=M[op[ qr[a][0] - qr[t][0] +1 ][ qr[a][1] -qr[t][1]+1 ]]+32;
a=t;
}
for(j=kk;j>=1;j--)
{
ans[++ak]=ansr[j];
}
aaa: ans[++ak]=M[ansb[i][0]];
mate[qu[ansb[i][2]].x ][qu[ansb[i][2]].y]='.';
rx=ex+move[ ansb[i][0] ][0],ry=ey+move[ansb[i][0]][1];
}
for(i=1;i<=ak;i++)putchar(ans[i]);
putchar(10);
}
int main()
{
int T=0,i;
for(i=0;i<4;i++)
{
op[ move[i][0]+1 ][ move[i][1]+1 ] = i;
}
while(cin>>m>>n ,m&&n)
{
printf("Maze #%d\n",++T);
solve();
putchar(10);
}
return 0;
}
不晓得怎么的 一直wa wa的
dis里面的数据都过了的
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator