PKU 3221 Diamond Puzzle

http://poj.org/problem?id=3221
図のような形のパズルがある。
このパズルの初期状態が与えられるので、空白のマスを移動させて図２のような状態にするのに必要な最短手数を求めろというような問題。

初期状態を基準に幅優先探索しました。

PI ed[]={mp(0,2),
         mp(0,4),
         mp(0,6),
         mp(1,2),
         mp(1,6),
         mp(2,3),
         mp(3,4),
         mp(4,5),
         mp(5,6),
};

int p10[10];

int next(int cst,int i,int j){
  int in=cst/p10[i]%10;
  int jn=cst/p10[j]%10;
  cst-=in*p10[i]+jn*p10[j];
  cst+=jn*p10[i]+in*p10[j];
  return cst;
}

main(){
  p10[6]=1;
  rep(i,6)p10[5-i]=p10[6-i]*10;
  map<int,int>app;
  queue<PI>q;
  q.push(mp(1234567,0));

  while(!q.empty()){
    int cst=q.front().F,cc=q.front().S;
    q.pop();
    if(app.count(cst))continue;
    app[cst]=cc;
    rep(i,9){
      if(cst/p10[ed[i].F]%10!=1 && cst/p10[ed[i].S]%10!=1)continue;
      int nst=next(cst,ed[i].F,ed[i].S);
      if(app.count(nst))continue;
      q.push(mp(nst,cc+1));
    }
  }

  int n;
  cin>>n;
  string in;
  rep(i,n){
    cin>>in;
    int st=0;
    rep(j,7)st=st*10+in[j]+1-'0';
    cout<<(app.count(st)?app[st]:-1)<<endl;
  }
}