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