题目大意：裸的八数码问题，让你输出空格的一条合法移动路径

首先利用康托展开对排列编号，可以预处理出排列，就不必逆展开了

然后利用A*算法求解

A*算法是一种启发式搜索，具体实现要用到优先队列/堆，不同于$dijkstra$，它的堆不是按照 初始状态向当前状态的花费$dis_{i}$进行贪心转移，而是额外处理出一个估值函数，处理出当前状态到目标状态花费的估计值$h_{i}$，然后按照$dis_{i}+h_{i}$排序，优先取出总和最小的。并且每个状态只会被搜索一次。如果搜索到了目标状态，立即跳出

这个过程，相当于我们取出一个全局较优解，虽然不一定是最优的，但大量减少了无用的搜索时间

而这道题的估值函数，可以粗略的计算为，每个数 当前状态的位置 到 目标状态的位置 的曼哈顿距离$(|xj-xi|+|yj-yi|)$ 之和

经过了A*优化的搜索，虽然不一定能搜出最短的路径，但极大减少了搜索的时间，因为搜的路径越短，我们搜索的总时间也越短，几乎是指数级别的优化。

然而A*也有弊端，如果存在无解的情况，A*就会退化成BFS，对所有状态都搜一次，而且多了一个常数$log$，在hdu上会T掉

所以我上网查了用了八数码判无解的方法，即对于去掉空格以后的8个数的排列，如果逆序对数量总和是奇数，则无解

证明大概是这样的，对于一个序列，任意交换两个相邻的数，逆序对数量的奇偶性不变，而八数码的表格扔到序列上，也满足这个性质

搞了大半个下午终于过了

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #define NN 370010  6 #define MM 100  7 #define ll long long   8 #define uint unsigned int  9 #define ull unsigned long long  10 #define inf 0x3f3f3f3f 11 using namespace std; 12  13 struct node{ 14     int id,d; 15     friend bool operator<(const node &s1,const node &s2) 16     {
   return s1.d>s2.d;} 17     node(int id,int d):id(id),d(d){} 18     node(){} 19 }; 20 int xx[4]={-1,0,1,0},yy[4]={
   0,1,0,-1}; 21 int f[NN][11],vis[NN],p[5][5],cnt; 22 int h[NN],g[NN],fa[NN],d[NN]; 23 int S[11],use[11],now[11],tmp[11],mu[11]; 24 inline int mabs(int x){
   return x>=0?x:-x;} 25 char ans[MM],c[4]={
   'u','r','d','l'}; 26  27 void dfs_permu(int dep) 28 { 29     if(dep==10){ 30         cnt++; 31         for(int i=1;i<=9;i++) 32             f[cnt][i]=now[i], 33             h[cnt]+=(mabs((i-1)/3-(now[i]-1)/3)+mabs((i-1)%3-(now[i]-1)%3)); 34         return; 35     } 36     for(int i=1;i<=9;i++) 37         if(!use[i]){ 38             use[i]=1,now[dep]=i; 39             dfs_permu(dep+1); 40             use[i]=0,now[dep]=0; 41         } 42 } 43 bool check(int x,int y) 44 {
   if(x<1||y<1||x>3||y>3)return 0;return 1;} 45 void Pre() 46 { 47     dfs_permu(1); 48     mu[1]=1; 49     for(int i=2;i<=9;i++) 50         mu[i]=mu[i-1]*i; 51 } 52 int s[100]; 53 void update(int x,int w){
   for(int i=x;i<=9;i+=(i&(-i)))s[i]+=w;} 54 int query(int x){
   int ans=0;for(int i=x;i>0;i-=(i&(-i)))ans+=s[i];return ans;} 55 int canter(int *tmp) 56 { 57     int ans=0; 58     for(int i=1;i<=9;i++) 59         update(i,1); 60     for(int i=1;i<=9;i++){ 61         ans+=query(tmp[i]-1)*mu[9-i]; 62         update(tmp[i],-1); 63     } 64     return ans+1; 65 } 66 int clr[NN],nn; 67 void init() 68 { 69     memset(ans,0,sizeof(ans)); 70     for(int i=1;i<=nn;i++){ 71         vis[clr[i]]=fa[clr[i]]=d[clr[i]]=0; 72         g[clr[i]]=inf; 73     }nn=0; 74 } 75  76 int main() 77 { 78     Pre(); 79     char str[10]; 80     priority_queue
         
          q; 81     nn=cnt; 82     for(int i=1;i<=nn;i++) clr[i]=i; 83     while(scanf("%s",str)!=EOF) 84     { 85      86     if('1'<=str[0]&&str[0]<='8') 87         S[1]=str[0]-'0'; 88     else S[1]=9; 89     for(int i=2;i<=9;i++) 90     { 91         scanf("%s",str); 92         if('1'<=str[0]&&str[0]<='8') 93             S[i]=str[0]-'0'; 94         else S[i]=9; 95     } 96     int invcnt=0; 97     for(int i=1;i<=9;i++) 98         for(int j=1;j
          
           S[i]) invcnt++;101 }102 if(invcnt&1){103 printf("unsolvable\n");104 continue;}105 init();106 int s,t,st,sx,sy,x,y;107 st=canter(S);108 if(st==1){109 puts("");110 continue;111 }112 q.push(node(st,h[st]));113 g[st]=0;114 while(!q.empty())115 {116 node k=q.top();q.pop();117 s=k.id;clr[++nn]=s;118 if(s==1) break;119 if(vis[s]) continue; vis[s]=1;120 for(int i=1;i<=9;i++)121 if(f[s][i]==9)122 sx=(i-1)/3+1,sy=(i-1)%3+1;123 for(int i=1;i<=9;i++)124 tmp[i]=f[s][i];125 for(int k=0;k<4;k++)126 {127 x=sx+xx[k],y=sy+yy[k];128 if(!check(x,y)) continue;129 swap(tmp[(x-1)*3+y],tmp[(sx-1)*3+sy]);130 int t=canter(tmp);131 if(g[t]>g[s]+1&&!vis[t]){132 g[t]=g[s]+1,fa[t]=s,d[t]=k;133 q.push(node(t,g[t]+h[t]));134 }135 swap(tmp[(x-1)*3+y],tmp[(sx-1)*3+sy]);136 }137 }138 while(!q.empty()){139 node k=q.top();q.pop();140 s=k.id;clr[++nn]=s;141 }142 if(!fa[1]){143 printf("unsolvable\n");144 continue;145 }146 t=1;int num=0;147 while(t!=st){148 ans[++num]=c[d[t]];149 t=fa[t];150 }151 for(int i=num;i>=1;i--)152 printf("%c",ans[i]);153 puts("");154 155 }156 157 return 0;158 }