PKU 3083 Children of the Candy Corn
http://poj.org/problem?id=3083
迷路が与えられる。
スタートからゴールまで壁に手をついてゴールを目指した場合を左の壁、右の壁の場合について何マス通るかと、最短経路が何マスなのかを答えるというような問題。
完全な実装探索ゲー。
左右をやるのは一つのループを使いまわしました。
string in[40]; main(){ int T; cin>>T; while(T--){ int h,w; cin>>w>>h; int sx,sy,sd; rep(i,h){ cin>>in[i]; rep(j,w)if(in[i][j]=='S'){ sx=i,sy=j; if(i==0)sd=1; if(i==h-1)sd=3; if(j==0)sd=0; if(j==w-1)sd=2; } } rep(i,2){ int cx=sx,cy=sy,cd=sd; int mi=1; if(i)mi=-1; int ti=0; int step=0; while(true){ ++step; if(in[cx][cy]=='E')break; rep(j,4){ int nx=cx+dx[(cd+mi*j+2+mi+8)%4],ny=cy+dy[(cd+mi*j+2+mi+8)%4]; if(in[nx][ny]=='#')continue; cx=nx,cy=ny; cd=(cd+mi*j+2+mi+8)%4; break; } } cout<<step<<' '; } queue<pair<PI,int> >q; q.push(mp(mp(sx,sy),0)); bool vis[h][w]; memset(vis,0,sizeof(vis)); while(!q.empty()){ int cx=q.front().F.F,cy=q.front().F.S,co=q.front().S; q.pop(); if(vis[cx][cy])continue; vis[cx][cy]=true; if(in[cx][cy]=='E'){ cout<<co+1<<endl; break; } rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || h<=nx || ny<0 || w<=ny || vis[nx][ny] || in[nx][ny]=='#')continue; q.push(mp(mp(nx,ny),co+1)); } } } }