参考文章：https://www.cnblogs.com/Inkblots/p/4846948.html
康托展开：https://blog.csdn.net/wbin233/article/details/72998375
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043
题意：给出一串数（有9个，其中有一个x），表示这些数再3*3的矩阵中的排序序列，如果可以通过交换x与其他数字的操作，
最终得到目的矩阵（eg：12345678x），就输出x的移动方向。分别用u表示向上，d表示向下，l向左，r向右。
思路：考察八数码的知识，由于数据总量可以接受，可以用bfs打表的方式先列出存在的每个情况，利用康托展开的映射关系（也就是每一个序列对应一个hash值）
来求出移动的方向。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std; #define MAX 400000
#define AIM 46234 //124567890对应的hash值 bool v[MAX];
char path[MAX][]; //总路径
int len; char dir[]="durl"; //反向搜索
int mov[][]={{-,},{,},{,-},{,}}; //八数码状态结构体
struct Node{
int s[];
int loc;
int status; //hash值排列值
int fa; //记录父状态
char d; //移动方向
};
Node n[MAX]; int fac[]={,,,,,,,,,}; //康托展开对应的hash值 int Inverse_cantor(int s[])
{
int sum=;
for(int i=;i<;i++)
{
int num=;
for(int j=i+;j<;j++) //逆序数计数器 （康托展开需要）
{
if(s[j]<s[i]) num++;
}
sum+=num*fac[-i-];
}
return sum+;
} void count_path(Node end) //反向记录路径
{
int status = end.status;
int f=end.fa;
len=;
path[status][len++]=end.d;
while(f)
{
path[status][len++]=n[f].d; //记录方向
f=n[f].fa; //查找父状态方向
}
} void BFS()
{
memset(v,,sizeof(v));
Node next;
int head=,tail=;
for(int i=;i<;i++) //目标状态
n[].s[i]=i+; n[].s[]=;
n[].loc=;//空位是8
n[].status=AIM;
v[AIM]=true;
while(head<=tail)
{
int x=n[head].loc/;
int y=n[head].loc%;
for(int i=;i<;i++) //遍历四个方向
{
int tx=x+mov[i][];
int ty=y+mov[i][];
if(tx<||tx>||ty<||ty>) continue; next=n[head]; //更新状态
next.loc=tx*+ty; //计算新空位
next.s[n[head].loc]=next.s[next.loc]; //原空位替换
next.s[next.loc]=; //新空位
next.fa=head;
next.d=dir[i];
next.status=Inverse_cantor(next.s);
//判断重复，并且新入队列
if(!v[next.status])
{
v[next.status]=true;
count_path(next);
n[++tail]=next;
}
}
head++;
}
} int main(void)
{
BFS();
char ch[];
Node cur;
while(~scanf("%s",ch))
{
if(!strcmp(ch,"x")) cur.s[]=,cur.loc=;
else cur.s[]=ch[]-'';
for(int i=;i<;i++)
{
scanf("%s",ch);
if(!strcmp(ch,"x"))
cur.s[i]=,cur.loc=i;
else cur.s[i]=ch[]-'';
}
cur.status=Inverse_cantor(cur.s);
if(v[cur.status])
printf("%s\n",path[cur.status]);
else printf("unsolvable\n");
}
return ;
}