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