PKU 3426 Doors and... more doors
http://poj.org/problem?id=3426
ドアが沢山ある迷路っぽいものの入力が与えられる。ドアを開ける向きによっては次にいけない方向がある。
最短で(1,1)から(n,n)まで行く道のりを示せというような問題。
次に移動できない方向と現在地でBFSして経路復元しました。
結構バグりました。
int can[1000][1000]; pair<PI,int> bef[1000][1000][4]; int fbd[1000][1000][4]; main(){ int n; cin>>n; rep(i,n)rep(j,n){ int t; cin>>t; if(t&1){ can[i][j] |= 1<<0; fbd[i][j][0] = t; } if(t==2 || t==4){ can[i][j+1] |= 1<<2; fbd[i][j+1][2] = t-1; } cin>>t; if(t&1){ can[i][j] |= 1<<3; fbd[i][j][3] = t-1; } if(t==2 || t==4){ can[i+1][j] |= 1<<1; fbd[i+1][j][1] = t-2; } } memset(bef,-1,sizeof(bef)); bef[0][0][1].S=0; queue<pair<PI,int> > q; q.push(mp(mp(0,0),1)); int cx,cy,fd=-1; while(!q.empty()){ cx=q.front().F.F,cy=q.front().F.S; fd=q.front().S; q.pop(); if(cx==n-1 && cy==n-1) break; rep(i,4){ if(fd==i) continue; int nx=cx+dx[i],ny=cy+dy[i]; if(~can[cx][cy]&(1<<i)) continue; int nfd=fbd[cx][cy][i]; if(bef[nx][ny][nfd].S!=-1) continue; //cout<<nx<<' '<<ny<<' '<<nfd<<endl; bef[nx][ny][nfd]=mp(mp(cx,cy),fd); q.push(mp(mp(nx,ny),nfd)); } } if(cx!=n-1 || cy!=n-1){ cout<<0<<endl; return 0; } vector<PI> ans; while(true){ ans.pb(mp(cx,cy)); if((cx|cy)==0) break; int nx=bef[cx][cy][fd].F.F; int ny=bef[cx][cy][fd].F.S; int nfd=bef[cx][cy][fd].S; cx=nx,cy=ny,fd=nfd; } reverse(ALL(ans)); FOR(it,ans) cout<<it->S+1<<' '<<it->F+1<<endl; }