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;
}