PKU 1166 The Clocks

http://poj.org/problem?id=1166
9個の時計の針を指定した数字コマンドで指定した位置を90度回転させることができる。
与えられた時計の状態に対して、全ての針が１２時を指すようにするための最短コマンドで、かつ辞書順最小なものを出力せよというような問題。

最短路探索+経路復元。
最初、場合分けがものすごく面倒くさいんじゃないかと思いましたが、そうでもありませんね。
時間はあまり余裕ではありませんでした。

bool vis[1<<18];
PI best[1<<18];

string rot[]={"ABDE",
              "ABC",
              "BCEF",
              "ADG",
              "BDEFH",
              "CFI",
              "DEGH",
              "GHI",
              "EFHI",
};

int up1(int st,int p){
  int pst=(st>>p*2)&3;
  pst=(pst+1)&3;
  st&=~(3<<p*2);
  return st|pst<<p*2;
}

main(){
  int st=0;
  rep(i,9){
    int t;
    cin>>t;
    st|=t<<i*2;
  }

  queue<pair<PI,int> >q;
  q.push(mp(mp(st,0),0));
  while(!q.empty()){
    int cst=q.front().F.F,be=q.front().F.S,op=q.front().S;
    q.pop();
    if(vis[cst])continue;
    vis[cst]=true;
    best[cst]=mp(be,op);
    if(cst==0)break;    
    rep(i,9){
      int nst=cst;
      rep(j,SZ(rot[i])){
        nst=up1(nst,rot[i][j]-'A');
      }
      if(vis[nst])continue;
      q.push(mp(mp(nst,cst),i));
    }
  }
  
  vector<int> ans;
  int go=0;
  while(true){
    PI tt=best[go];
    go=tt.F;
    ans.pb(tt.S);
    if(st==go)break;
  }
  reverse(ALL(ans));
  rep(i,SZ(ans)){
    if(i)cout<<' ';
    cout<<ans[i]+1;
  }
  cout<<endl;
}