题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043
解题思路：反向BFS + 康托展开
从目标状态 “1 2 3 4 5 6 7 8 x" 反过来做BFS，记录其可能访问到的状态，用康托展开为每一个状态 ”编码“（我不知道怎么说比较合适，其实就是找一个数来代表这个状态），用 fa 来记录每个状态的上一个状态，方便读取转移路径。思路不难，实现难！
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=500000; 7 const int cx[4]={0,0,1,-1},cy[4]={1,-1,0,0}; 8 const int factor[]={ 1,1,2,6,24,120,720,5040,40320,362880 }; 9 char go[6]="lrud"; 10 struct state{ 11 int s[10]; 12 int fa,pos,cnum; 13 char nowc; 14 }ku[maxn]; 15 int vis[maxn]; 16 char ans[1000]; 17 int cantor(int x[9]){ 18 int sum=0,s; 19 for(int i=0;i<9;i++){ 20 s=0; 21 for(int j=i+1;j<9;j++){ 22 if(x[j]<x[i]) s++; 23 } 24 sum+=s*factor[9-i-1]; 25 } 26 return sum+1; 27 } 28 void init(){ 29 memset(vis,0,sizeof(vis)); 30 for(int i=0;i<8;i++) ku[0].s[i]=i+1; 31 ku[0].s[8]=0; 32 ku[0].fa=-1,ku[0].pos=8; 33 ku[0].cnum=cantor(ku[0].s); 34 int head=0,ending=1; 35 while(head<ending){ 36 state now=ku[head]; 37 int x=now.pos/3,y=now.pos%3; 38 for(int i=0;i<4;i++){ 39 state next; 40 int dx=x+cx[i],dy=y+cy[i]; 41 if(dx<0||dx>=3||dy<0||dy>=3) continue; 42 next.pos=dx*3+dy; 43 for(int j=0;j<9;j++) next.s[j]=now.s[j]; 44 swap(next.s[next.pos],next.s[now.pos]); 45 next.cnum=cantor(next.s); 46 if(!vis[next.cnum]){ 47 next.fa=head; 48 next.nowc=go[i]; 49 ku[ending]=next; 50 vis[next.cnum]=ending; 51 ending++; 52 } 53 } 54 head++; 55 } 56 } 57 void find_root(int t){ 58 int ind=0; 59 t=vis[t]; 60 for(;ku[t].fa!=-1;t=ku[t].fa,ind++) 61 ans[ind]=ku[t].nowc; 62 } 63 int main() 64 { 65 init(); 66 char input[30]; 67 int ins[9]; 68 while(gets(input)){ 69 int ind=0,l=strlen(input); 70 for(int i=0;i<l;i++){ 71 if(input[i]=='x') ins[ind++]=0; 72 else if(input[i]>'0'&&input[i]<'9') ins[ind++]=input[i]-'0'; 73 } 74 int tt=cantor(ins); 75 if(!vis[tt]) printf("unsolvable "); 76 else{ 77 memset(ans,0,sizeof(ans)); 78 find_root(tt); 79 printf("%s ",ans); 80 } 81 } 82 return 0; 83 }