http://acm.hdu.edu.cn/showproblem.php?pid=1043
http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html
根据这篇文章说的八数码八境界,我这种做法大概是在境界三。。
我选择的是康托展开作为哈希函数,在全排列问题中这个哈希函数可以很好的处理冲突
http://zh.wikipedia.org/zh/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80
当然白书上的那种哈希也是极好的。。
#include <iostream> #include <queue> #include <cstring> using namespace std ; int vis[1000005] ; int f[10]={1,1,2,6,24,120,720,5040,40320,362880} ; int ct(int *a) { int ans=0 ; for(int i=0 ;i<8 ;i++) { int cnt=0 ; for(int j=i+1 ;j<9 ;j++) if(a[j]<a[i]) cnt++ ; ans+=cnt*f[8-i] ; } return ans ; } typedef struct L{ int a[10] ; int p,pos ; string step ; }L ; int dx[]={1,-1,0,0} ; int dy[]={0,0,1,-1} ; string d="udlr" ; string ans[1000005] ; void bfs() { queue <L> q ; L now,next ; for(int i=0 ;i<8 ;i++) now.a[i]=i+1 ; now.a[8]=0 ; now.p=ct(now.a) ; now.pos=8 ; now.step="" ; ans[now.p]="" ; q.push(now) ; vis[now.p]=1 ; while(!q.empty()) { now=q.front() ; q.pop() ; for(int i=0 ;i<4 ;i++) { int xx=now.pos/3+dx[i] ; int yy=now.pos%3+dy[i] ; if(xx<0 || xx>2 || yy<0 || yy>2)continue ; next=now ; next.pos=xx*3+yy ; next.a[now.pos]=next.a[next.pos] ; next.a[next.pos]=0 ; next.p=ct(next.a) ; if(!vis[next.p]) { next.step+=d[i] ; vis[next.p]=1 ; ans[next.p]=next.step ; q.push(next) ; } } } } void pt(int *a) { int tt=ct(a) ; if(!vis[tt]) { puts("unsolvable") ; return ; } for(int i=ans[tt].length()-1 ;i>=0 ;i--) cout << ans[tt][i] ; putchar(‘\n‘) ; } int main() { bfs() ; char s[101] ; while(gets(s)) { int st=0 ; int t[10] ; for(int i=0 ;i<strlen(s) ;i++) { if(s[i]>=‘1‘ && s[i]<=‘8‘) t[st++]=s[i]-‘0‘ ; if(s[i]==‘x‘) t[st++]=0 ; } pt(t) ; } return 0 ; }