测试地址：Eight
题目大意：一个3*3的棋盘上有8个格子写着1~8的数字，还有一个空格，给定局面，要求给出一个空格的移动序列，使得达到目标状态：
1 2 3
4 5 6
7 8 x（空格）
做法：大名鼎鼎的八数码问题...学习了A*算法后，今天特意去试做了了下，居然过了，数据好水啊...
题目中的状态可以用0~8的全排列表示，可以将其与1~9!的数字来进行映射，这就需要用到一种叫做康托展开的优秀的哈希算法。具体过程就不再赘述了，网上很容易可以找到过程。
然后就是设计估价函数。f=g+h，其中g为从起始状态走到当前状态的步数，h为每一个数字的位置与其在目标状态中位置的曼哈顿距离之和。然后就可以进行搜索了。
据说好像有比裸搜更快捷的判定无解的方法...然而我看的资料里的方法是错的，有待学习有待学习...
以下是本人代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct state {int s[10];} a,t;
struct statement
{
int s,g,h;
bool operator < (statement a) const
{
return a.g+a.h<g+h;
}
};
int start,f[400000],fa[400000];
bool flag=0;
void read()
{
int i=1;char c;
while(scanf("%c",&c)!=EOF&&i<=9)
{
if (c==' ') continue;
if (c=='x') a.s[i]=0;
else a.s[i]=c-'0';
i++;
}
}
int cantor(state a)
{
int fac[11]={1,1,2,6,24,120,720,5040,40320,362880,3628800};
int s=0;
for(int i=1;i<=9;i++)
{
int tmp=0;
for(int j=i+1;j<=9;j++)
if (a.s[j]<a.s[i]) tmp++;
s+=tmp*fac[9-i];
}
return s+1;
}
state q_cantor(int a)
{
int fac[11]={1,1,2,6,24,120,720,5040,40320,362880,3628800};
state s;
a--;
bool vis[10]={0};
for(int i=1;i<=9;i++)
{
int tmp=a/fac[9-i],f=0;
for(int j=0;j<=8;j++)
if (!vis[j])
{
f++;
if (f==tmp+1)
{
vis[j]=1;
s.s[i]=j;
break;
}
}
a=a%fac[9-i];
}
return s;
}
int calc_h(state a)
{
int s=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
{
int k=a.s[(i-1)*3+j];
if (k==0) s+=abs(3-i)+abs(3-j);
else
{
int q=k/3,r=k%3;
if (r==0) q--,r=3;
s+=abs(q+1-i)+abs(r-j);
}
}
return s;
}
void outputpath(int t,int g)
{
int i=t;
char route[10000];
flag=1;
for(int j=g;j>=1;j--)
{
state x=q_cantor(i),fx=q_cantor(fa[i]);
int x1,x2;
for(int k=1;k<=9;k++) if (x.s[k]==0) {x1=k;break;}
for(int k=1;k<=9;k++) if (fx.s[k]==0) {x2=k;break;}
if (x1-x2==3) route[j]='d';
if (x1-x2==-3) route[j]='u';
if (x1-x2==1) route[j]='r';
if (x1-x2==-1) route[j]='l';
i=fa[i];
}
for(int i=1;i<=g;i++) printf("%c",route[i]);
}
void AStar()
{
memset(f,0x7f,sizeof(f));
priority_queue<statement> Q;
statement now,next;
now.s=start,now.g=0,now.h=calc_h(a);
Q.push(now);
while(!Q.empty())
{
now=Q.top();
Q.pop();
if (now.s==cantor(t)) {outputpath(now.s,now.g);break;}
state st=q_cantor(now.s);
int x;
for(int i=1;i<=9;i++) if (st.s[i]==0) {x=i;break;}
if (x-3>0)
{
swap(st.s[x],st.s[x-3]);
next.s=cantor(st),next.g=now.g+1,next.h=calc_h(st);
if (next.g+next.h<f[next.s])
{
fa[next.s]=now.s;
f[next.s]=next.g+next.h;
Q.push(next);
}
swap(st.s[x],st.s[x-3]);
}
if (x+3<=9)
{
swap(st.s[x],st.s[x+3]);
next.s=cantor(st),next.g=now.g+1,next.h=calc_h(st);
if (next.g+next.h<f[next.s])
{
fa[next.s]=now.s;
f[next.s]=next.g+next.h;
Q.push(next);
}
swap(st.s[x],st.s[x+3]);
}
if (x%3!=1)
{
swap(st.s[x],st.s[x-1]);
next.s=cantor(st),next.g=now.g+1,next.h=calc_h(st);
if (next.g+next.h<f[next.s])
{
fa[next.s]=now.s;
f[next.s]=next.g+next.h;
Q.push(next);
}
swap(st.s[x],st.s[x-1]);
}
if (x%3!=0)
{
swap(st.s[x],st.s[x+1]);
next.s=cantor(st),next.g=now.g+1,next.h=calc_h(st);
if (next.g+next.h<f[next.s])
{
fa[next.s]=now.s;
f[next.s]=next.g+next.h;
Q.push(next);
}
swap(st.s[x],st.s[x+1]);
}
}
}
int main()
{
read();
t.s[1]=1;t.s[2]=2;t.s[3]=3;t.s[4]=4;t.s[5]=5;
t.s[6]=6;t.s[7]=7;t.s[8]=8;t.s[9]=0;
start=cantor(a);
AStar();
if (!flag) printf("unsolvable");
return 0;
}