PKU 2935 Basic Wall Maze
http://poj.org/problem?id=2935
迷路の最短経路を出力する問題。
壁の処理が面倒くさい。
去年のICPCの国内予選問題のやつより少し難易度高い気がします。
int cost[20][20]; bool wa[20][20]; main(){ int sx,sy,ex,ey; while(cin>>sx>>sy,sx|sy){ cin>>ex>>ey; --sx,--sy,--ex,--ey; memset(cost,0,sizeof(cost)); memset(wa,0,sizeof(wa)); rep(i,3){ int ksx,ksy,kex,key; cin>>ksx>>ksy>>kex>>key; if(ksx==kex){ for(int y=ksy;y<key;y++)wa[ksx*2][y]=1; }else{ for(int x=ksx*2+1;x<kex*2;x+=2)wa[x][key]=1; } } queue<pair<int,PI> > q; q.push(mp(1,mp(sx,sy))); while(!q.empty()){ int cc=q.front().F,cx=q.front().S.F,cy=q.front().S.S; q.pop(); if(cost[cx][cy])continue; cost[cx][cy]=cc; rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || 6<=nx || ny<0 || 6<=ny || cost[nx][ny])continue; if(nx==cx){ if(wa[2*nx+1][(ny+cy)/2+1])continue; q.push(mp(cc+1,mp(nx,ny))); }else{ if(wa[(nx+cx)+1][ny])continue; q.push(mp(cc+1,mp(nx,ny))); } } } string out; int cx=ex,cy=ey; string dir="NWSE"; while(cx!=sx || cy!=sy){ rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || 6<=nx || ny<0 || 6<=ny || cost[nx][ny]+1!=cost[cx][cy])continue; if(nx==cx){ if(wa[2*nx+1][(ny+cy)/2+1])continue; out+=dir[i]; cx=nx; cy=ny; break; }else{ if(wa[(nx+cx)+1][ny])continue; out+=dir[i]; cx=nx; cy=ny; break; } } } reverse(ALL(out)); cout<<out<<endl; } }