PKU 1077 Eight

http://poj.org/problem?id=1077
8パズルの解答手順を答えろというような問題。

最初マスを移動させるのとは全く逆のパターンを出力してしまっていてWAをだし続け、一回だけTLEになったのでmapをやめてハッシュで頑張ったりしました。
ハッシュ書くの若干飽きてきました。

typedef struct _node{
  int key;
  int F,S;
  _node*next;
}node;

const int MOD=1000007;
node*hash[MOD];
node ent[1000000];
int sz;

void insert(int key,int be,int op){
  int ha=key%MOD;
  for(node*p=hash[ha];p;p=p->next){
    if(p->key==key){
      return;
    }
  }
  node*p=hash[ha];
  hash[ha]=ent+sz++;
  hash[ha]->next=p;
  hash[ha]->key=key;
  hash[ha]->F=be;
  hash[ha]->S=op;
}

node* get(int key){
  int ha=key%MOD;
  for(node*p=hash[ha];p;p=p->next){
    if(p->key==key)
      return p;
  }
  return 0;
}

int po[10];

int next(int in,int p,int q){
  int pi=(in/po[8-p])%10;
  int qi=(in/po[8-q])%10;
  int ret=0,base=1;
  rep(i,9){
    int c=in%10;in/=10;
    if(i==8-p)c=qi;
    if(i==8-q)c=pi;
    ret+=c*base;
    base*=10;
  }
  return ret;
}

main(){
  int st=0;
  int sp;
  po[0]=1;
  rep(i,9){
    po[i+1]=po[i]*10;
    char c;
    cin>>c;
    if(c=='x')c='9',sp=i;
    st=st*10+c-'0';
  }

  queue<pair<PI,PI > >q;
  char dir[]={'l','u','r','d'};

  q.push(mp(mp(123456789,8),mp(0,0)));

  while(!q.empty()){
    int cs=q.front().F.F;
    int i=q.front().F.S;
    int be=q.front().S.F;
    int bop=q.front().S.S;
    q.pop();
    if(get(cs))continue;
    insert(cs,be,bop);
    
    int cx=i/3,cy=i%3;
    rep(j,4){
      int nx=cx+dx[j],ny=cy+dy[j];
      if(nx<0 || 3<=nx ||
         ny<0 || 3<=ny)continue;
      int sw=nx*3+ny;
      int ns=next(cs,i,sw);
      if(get(ns))continue;
      q.push(mp(mp(ns,sw),mp(cs,j)));
    }
  }

  if(!get(st))cout<<"unsolvable"<<endl;
  else{
    vector<char>ans;
    while(true){
      if(st==123456789)break;
      node*p=get(st);
      ans.pb(dir[p->S]);
      st=p->F;
    }
    rep(i,SZ(ans))cout<<ans[i];
    cout<<endl;
  }
}