题目来源：
http://poj.org/problem?id=1077
题目大意：
给你一个由1到8和x组成的3*3矩阵，x每次可以上下左右四个方向交换。求一条路径，得到12345678x这样的矩阵。若没有路径，则输出unsolvable。
经典的八数码问题。
这题我用A*算法做的。推荐一篇博客，从大体上介绍了一下启发式算法的代表A*算法：
https://www.cnblogs.com/zhoug2020/p/3468167.html
首先就是判重的问题，搜索的状态是九个数（含x），开个九重数组也不是不可以，但用cantor展开hash一下还是方便的。所谓cantor展开，就是对1..n的所有排列，唯一对应一个1..n!的值。
cantor展开解决互不相同的元素的全排列问题（互不相同就可以了）。代码中的cantor展开，可以当做模板用。
康托展开的公式是 X=a1*(n-1)!+a2*(n-2)!+...+ai*(i-1)!+...+an-1*1!+an*0! 其中，ai为当前元素比之后多少个元素大。
其实理解公式很简单，给你排列2,4,1,5,3，你可以这么想，第一个放2，说明1开头的都排完了，至少比4！种排列靠后了，第二个数是4，说明2,1开头和2,3开头的都排过了，又比2*3！种排列靠后了。以此类推。。
其次就是奇偶剪枝了。奇偶剪枝是一个常见的预判断的方法。接下来详细阐述一下：
1、逆序数的概念
给定数列a[1..n]，记LESS(i)为a[i+1]到a[n]中比a[i]小的数的个数，则逆序数为∑LESS(i)。比如有数列a[1..5]=[3,7,2,19,2]，则LESS(1)到LESS(5)分别为2,2,0,1,0，所以逆序数为2+2+0+1+0=5。
2、树状数组（线段树）求逆序数
将值val与序号id放在结构体中一起排序，先按值的升序排列，值相同时，再按序号升序排列（这样后面求LESS值的时候不会把相同的数算进去）。
比如a[1..5]=[3,7,2,19,2]，排序成[2:3,2:5,3:1,7:2,19:4]（冒号后为排序用结构体里的id）。
然后维护[1..n]的树状数组。初始全为0，顺序遍历排好序的结构体，将id处的值变为1，并查询i+1到n的和，即可得到LESS值，再将LESS值求和，即可。
比如上例顺序执行可得LESS(3)=0,LESS(5)=0,LESS(1)=2,LESS(2)=2,LESS(4)=1。逆序数为5。
3、八数码的奇偶剪枝
对于1..n的排列，交换相邻的元素，逆序数奇偶性一定改变。所以如果将八数码中的x视作9的话，八数码可以看成是1..9的排列。左右交换，是一次相邻元素的交换，上下交换，可以看成3+2=5次相邻交换，逆序数奇偶性一定改变。
现在我们改变一下1中对LESS(i)的定义，重定义为对于数i，LESS(i)为从它的位置到最后比它小的数的个数。由于现在的排列没有相同的数，所以求和得到的逆序数是不变的。
如果从1..9的排列中除去9，可以发现1..8的LESS值不变，而上下/左右交换前后LESS(9)的奇偶性一定改变，又结合之前交换前后逆序数奇偶性改变，得到1..8逆序数奇偶性不变。
还有一个15迷的问题，奇偶剪枝也是一样的分析思路，只是加了个辅助量。
最后就是Astar算法本身了：
首先需要一个优先队列。由于对优先级的需要，我们需要在结构体中对<运算符进行重载（详见代码）。
然后结构体中存储路径最好还是用string吧，毕竟vector还是没它方便。
好像就是这么多。搜索这种东西，复杂度比较难把握，所以能优化的地方尽量优化一下吧。比如搜索方向，感觉还是先搜索down和right比较好，虽然可能效果不太明显。
这道题还要继续做。hdu1043还没A掉，双向BFS，还有什么打表方法还没有尝试写呢。加上！！！，表示要记得做！
#include<iostream> #include<cstdio> #include<string> #include<queue> #include<cstring> using namespace std; char buf[30]; int puz[9]; int fac[]={1,1,2,6,24,120,720,5040,40320,362880}; int cantor(int s[]) { int sum=0; for(int i=0;i<9;i++) { int num=0; for(int j=i+1;j<9;j++) if(s[j]<s[i]) num++; sum+=(num*fac[9-i-1]); } return sum+1; } struct tnode { int puz[9]; string path; int loc;//0的位置 int status;//cantor展开值 int n;//搜索深度 int f;//估值函数 int getloc() { for(int i=0;i<9;i++) if(puz[i]==0) return i; } bool operator<(const tnode& y) const { return f>y.f; } }; int vis[363000]; int dis[9]={4,3,2,3,2,1,2,1,0}; int a[4]={1,3,-1,-3}; char b[5]="rdlu"; int aim=46234; int main() { while(scanf("%[^ ]",buf)!=EOF) { getchar(); for(int i=0,cnt=0;buf[i]!=' ';i++) { if(buf[i]=='x') puz[cnt++]=0;//用0存储x else if(buf[i]>='1'&&buf[i]<='8') puz[cnt++]=buf[i]-'0'; } //for(int i=0;i<9;i++) printf("%d ",puz[i]); printf(" "); //printf("%d ",cantor(puz)); int cnt=0; for(int i=0;i<9;i++) if(puz[i]!=0) { for(int j=i+1;j<9;j++) if(puz[j]!=0&&puz[j]<puz[i]) cnt++; } if(cnt%2==1) { printf("unsolvable "); continue; } priority_queue<tnode> q; memset(vis,0,sizeof(vis)); tnode node1; memcpy(node1.puz,puz,sizeof(puz)); node1.path=""; node1.loc=node1.getloc(); node1.status=cantor(node1.puz); node1.n=0; node1.f=node1.n+dis[node1.loc]; if(node1.status==aim)//入队之前先判断，可以加快速度 { cout<<node1.path<<endl; continue; } q.push(node1); vis[node1.status]=1; bool flag=false; while(!q.empty()) { tnode node2=q.top();q.pop(); bool fflag=false; for(int i=0;i<4;i++) { tnode node3=node2; //printf("%d ",node3.loc); if(a[i]==1&&node3.loc%3<=1) { node3.puz[node3.loc]=node3.puz[node3.loc+a[i]]; node3.puz[node3.loc+a[i]]=0; node3.status=cantor(node3.puz); } else if(a[i]==-1&&node3.loc%3>=1) { node3.puz[node3.loc]=node3.puz[node3.loc+a[i]]; node3.puz[node3.loc+a[i]]=0; node3.status=cantor(node3.puz); } else if(a[i]==3&&node3.loc<=5) { node3.puz[node3.loc]=node3.puz[node3.loc+a[i]]; node3.puz[node3.loc+a[i]]=0; node3.status=cantor(node3.puz); } else if(a[i]==-3&&node3.loc>=3) { node3.puz[node3.loc]=node3.puz[node3.loc+a[i]]; node3.puz[node3.loc+a[i]]=0; node3.status=cantor(node3.puz); } //printf("%d ",node3.status); if(!vis[node3.status]) { node3.path+=b[i]; node3.loc=node3.getloc(); node3.n++; node3.f=node3.n+dis[node3.loc]; q.push(node3); vis[node3.status]=1; } if(node3.status==aim) { node1=node3; fflag=true; break; } } if(fflag) { flag=true; break; } } if(flag) { cout<<node1.path<<endl; } else { printf("unsolvable "); } } return 0; }