题目：http://acm.hdu.edu.cn/showproblem.php?pid=1043
说实话，这道题我算是写了很久了，这道题当然也让我收获甚多，作为新手，刚开始的话，我是用 map<string,int>作为标识，显然这样是行不通的。直到后来，百度上意外搜到了bin神的代码，运用逆序枚举的方法，后面直接打表就行行了，我提交的代码：http://blog.csdn.net/i_am_a_winer/article/details/43890231
当然，打表的方法不用判断所谓的有无解的问题，因为，我们已经枚举了出了所有可行的起点，只要是能到达终点状态的起点，其vis在枚举时已经变成了 1。
看到，有人说：八数码问题决定了一生是否完美的。这足以说明，此题的重要性。
所以我有决定用其他代码来解决此问题：A* 和 双 BFS，顺便学习这两种算法，可是这样以来问题就又来了，第一次写的双BFS（凭感觉写的）一提交就TLE了，当然这是第一次写的，错就错吧，水平问题。那我就先学习A*算法把，看了其他人的代码，发现这里有一个新的知识点：八数码的逆序数问题，因为这个问题决定了整个程序的效率问题，否则，不管你用的什么搜索，只要是遇到无解的情况时，都得搜个遍，那么何来谁更快的说法呢！到了这里，我似乎觉得我第一次写的双BFS TLE的原因了：没有判断是否有解！
这里添加一些关于八数码的逆序数问题的知识点：原文链接：http://blog.csdn.net/ju136/article/details/6876647
对于给定八数码棋局的初始状态，我们的目标是通过交换空格与其相邻棋子使棋盘达到目标状态。
其中，游戏规则是只能交换空格与其上下左右四个方向的相邻棋子。
假设棋局目标状态为如下形式：（A、B、C、D、E、F、G、H表示棋子）
A B C
D E F
G H
而初始状态就是A、B、C、D、E、F、G、H这八个棋子在这九个棋格上的任意分布。
并且我们对棋盘中每个棋格进行如下形式的编号：
1 2 3
4 5 6
7 8 9
那么，对于一个任意的棋局状态，我们可以取得这八个棋子（A、B、C、D、E、F、G、H）的一个数列：棋子按照棋格的编号依次进行排列，记为p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8]（即A、B、C、D、E、F、G、H的一个排列）。
在分析之前，先引进逆序和逆序数的概念：对于棋子数列中任何一个棋子c[i]（1≤i≤8），如果有j>i且c[j]<c[i]，那么 c[j]是c[i]的一个逆序，或者c i]和c[j]构成一个逆序对。定义棋子c[i]的逆序数为c[i]的逆序个数；棋子数列的逆序数为该数列所有棋子的逆序数总和。注：约定A<B<C<D<E<F<G<H。
现在，我们对一个任意的棋局状态p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8]进行分析：
引理1：如果交换任何两个相邻的棋子，那么棋子数列的逆序数将发生奇偶性互变（奇偶性互变是指由奇数变为偶数，或由偶数变为奇数，下同）。
其证明很简单，假设交换的是c[i]和c[i+1]，那么对于c[j]（1≤j≤i-1或i+2≤j≤8）的逆序数并不改变。若交换之前 c[i]<c[i+1]，那么交换之后，c[i]的逆序数不变，而c[i+1]的逆序数加1（因为c[i]成了它的一个逆序）；同理，若交换之前 c[i]>c[i+1]，那么交换之后，c[i]的逆序数减1，而c[i+1]的逆序数不变。所以，引理1成立。
引理2：如果棋子数列经过n次相邻棋子交换后，若n为偶数，则数列逆序数奇偶性不变；若n为奇数，则数列逆序数将发生奇偶性互变。
其证明可以由引理1简单推出。
引理3：在满足上述约定的八数码问题中，空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。
证明：显然空格与左右棋子交换不会改变棋子数列的逆序数（因为数列并没有改变）。现在考虑空格与上下棋子交换的情况：若空格与上方的棋子交换（假设交换是可行的），将得到一个新数列。若假设交换棋子为c[i]=X，那么原数列p=c[1]...X c[i+1]c[i+2]...c[8]将变为新数列q=c[1]...c[i+1]c[i+2]X ...c[8]（注意：在棋盘中，上下相邻的两棋格之间隔有两个棋格）。由原数列p到新数列q的转变可以通过如下方式加以解释：用X与c[i+1]、 c[i+2]先后进行两次相邻交换而完成状态转变。所以根据引理2知，由p状态到q状态并不会改变改变棋子数列的逆序数的奇偶性。同理可证空格与下方棋子交换也不会改变棋子数列的逆序数的奇偶性。所以，空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。
定理1
（1）当初始状态棋局的棋子数列的逆序数是奇数时，八数码问题无解；
（2）当初始状态棋局的棋子数列的逆序数是偶数时，八数码问题有解。
证明：由引理3知，按照八数码问题的游戏规则，在游戏过程中，棋局的棋子数列的逆序数的奇偶性不会发生变化。而上面规定的目标状态没有逆序存在，所以目标状态下棋局的逆序数为偶数（实际为0）。显然，可能的初始状态棋局的棋子数列的逆序数可能为奇数，也可能为偶数（因为把一个初始状态中任意相邻两个棋子交换，得到的新的状态作为初始状态，它们的奇偶性相反）。所以，对于任意一个初始状态，若其棋局的棋子数列的逆序数为奇数，则永远也不可能达到目标状态，即八数码问题无解；若其棋局的棋子数列的逆序数为偶数，（接下来如何证明）。
A*算法代码：
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int s[9];
int cur,n;//分别表示0的位置，和当前hash值（即cantor函数的值）
int f,g,h;//即A*算法的f,g,h
node(){}
bool operator <(const node &a)const{
if(a.f!=f) return a.f<f;
return a.g<g;
}
}o;
int fac[]={1,1,2,6,24,120,720,5040,40320};
int cantor(int s[]){//康托展开，即一个状态压缩的Hash函数
int sum=0;
for(int i=0;i<9;i++){
int cnt=0;
for(int j=i+1;j<9;j++)
if(s[j]<s[i]) cnt++;
sum+=cnt*fac[9-i-1];
}
return sum;
}
int get_h(int s[]){//A*算法的乐观估价函数，这里用的是曼哈顿距离公式
int val=0;
for(int i=0;i<9;i++){//这里有9个点数字需要回到目标状态
int x=i/3,y=i%3;//数字状态当前所在坐标
if(s[i]){
int tx=(s[i]-1)/3,ty=(s[i]-1)%3;//数字目标状态所在坐标
val+=abs(x-tx)+abs(y-ty);
}
}
return val;
}
int vis[363000];
int d[][2]={{1,0},{-1,0},{0,-1},{0,1}};
char dir[]="dulr";
int front[363000];//记录路径
char path[363000];//记录路径的值
void disp(int n){//打印解
if(front[n]){
disp(front[n]);
cout<<path[n];
}
}
void bfs(){//A*算法也是一种层次遍历，只是把宽度变窄了，所以写作BFS应该也还好理解
memset(vis,0,sizeof(vis));
memset(front,0,sizeof(front));
priority_queue<node> q;
q.push(o);
vis[o.n]=1;
int ans=46233;//“123456780“的hash值
while(!q.empty())
{
node tmp=q.top();
if(tmp.n==ans){
disp(ans);
cout<<endl;
return;
}
q.pop();
int x=tmp.cur/3,y=tmp.cur%3;
for(int p=0;p<4;p++){
int tx=d[p][0]+x,ty=d[p][1]+y;
if(tx<0 || ty<0 || tx>2 || ty>2) continue;
node tmp2=tmp;
tmp2.cur=tx*3+ty;
swap(tmp2.s[tmp.cur],tmp2.s[tmp2.cur]);
tmp2.n=cantor(tmp2.s);
if(vis[tmp2.n]) continue;
vis[tmp2.n]=1;
front[tmp2.n]=tmp.n;
path[tmp2.n]=dir[p];
tmp2.g++;tmp2.h=get_h(tmp2.s);tmp2.f=tmp2.g+tmp2.h;
q.push(tmp2);
}
}
//cout<<"No\n";
}
int main(){
char ch;
while(cin>>ch){
if(ch=='x'){
ch='0';
o.cur=0;
}
o.s[0]=ch-'0';
for(int i=1;i<9;i++){
cin>>ch;
if(ch=='x'){
ch='0';
o.cur=i;
}
o.s[i]=ch-'0';
}
o.n=cantor(o.s);
o.g=0;o.h=get_h(o.s);o.f=o.g+o.h;
int cnt=0;
for(int i=0;i<8;i++)//记录逆序数
if(o.s[i])
for(int j=i+1;j<9;j++)
if(o.s[j]<o.s[i] && o.s[j]) cnt++;
if(cnt&1) cout<<"unsolvable\n";
else bfs();
}
return 0;
}
双BFS代码：
这里我有个疑惑：既然双BFS可行，那么必然存在某一个状态到目标状态的层次最深，不妨设为Max，由于是前后一起遍历，前后分别遍历的最大层次为Max/2（Max为偶数）或 Max/2+1（Max为奇数），所以当下面程序中的 L>Max/2+1 时，结束while表示无解不就行了吗？这样一来不久可以不用进行八数码的逆序数无解判断了吗？（虽然这样更快）
可事实并不是这样，提交时，L=13时，WA，L=14时，TLE。下面这个代码时间是1.2s左右。这个疑惑还待解决哦！！!
当然，写到这里，我忽然想到了既然都是搜索，是否可以用双A*算法呢？效率如何呢？
A*是把层次变窄了，所以较快，双A*和单A*应该差不多，因为那和单 A*相比，在路径上没有什么改变，仅仅hi该边了遍历的方向。
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
int vis1[363000],vis2[363000];
int ed[]={1,2,3,4,5,6,7,8,0};
string path[363000];//记录路径
int cantor(int s[]){//康托展开，进行状态压缩
int sum=0;
for(int i=0;i<9;i++){
int cnt=0;
for(int j=i+1;j<9;j++)
if(s[j]<s[i]) cnt++;
sum+=cnt*fac[9-i-1];
}
return sum;
}
struct node{
int s[9];
int cur,n;//同A*算法
int deep;//记录所在层次
}o;
int d[][2]={{1,0},{-1,0},{0,-1},{0,1}};
char dr1[]="dulr",dr2[]="udrl";//这里前后遍历的方向相反，路径也相反
void bfs(){//可以看出，双BFS的前后代码几乎是对称的，vis两个，队列两个
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
queue<node> q,qq;
q.push(o);
vis1[o.n]=1;
path[o.n]="";
memcpy(o.s,ed,sizeof(o.s));
o.n=cantor(o.s);
o.cur=8;
o.deep=0;
path[o.n]="";
qq.push(o);
vis2[o.n]=1;
int L=0;//记录层次，既然是双向的，肯定是你一层，我一层的顺序依次进行
while(!q.empty() || !qq.empty()){
while(q.front().deep==L){
node tmp=q.front();
q.pop();
int x=tmp.cur/3,y=tmp.cur%3;
for(int p=0;p<4;p++){
int tx=x+d[p][0],ty=y+d[p][1];
if(tx<0 || ty<0 || tx>2 || ty>2) continue;
node tmp2=tmp;
tmp2.cur=tx*3+ty;
swap(tmp2.s[tmp.cur],tmp2.s[tmp2.cur]);
tmp2.n=cantor(tmp2.s);
tmp2.deep=tmp.deep+1;
if(vis2[tmp2.n]){//这里判断相遇，如果逆序遍历已经达到了这里，则路径连通，找到了解
reverse(path[tmp2.n].begin(),path[tmp2.n].end());//这里得注意相遇点路径的记录
cout<<path[tmp.n]<<dr1[p]<<path[tmp2.n]<<endl;//方法，因为这里只有一个path，既然
return;//tmp2.n已经存在于逆需遍历的路径中，我们不能再对其操作，否则会导致后面已经记录
}//的路径丢失，只能单独输出
if(vis1[tmp2.n]) continue;
vis1[tmp2.n]=1;
path[tmp2.n]=path[tmp.n];
path[tmp2.n]+=dr1[p];
q.push(tmp2);
}
}
while(qq.front().deep==L){//上下代码对称，原理也是一样的
node tmp=qq.front();
qq.pop();
int x=tmp.cur/3,y=tmp.cur%3;
for(int p=0;p<4;p++){
int tx=x+d[p][0],ty=y+d[p][1];
if(tx<0 || ty<0 || tx>2 || ty>2) continue;
node tmp2=tmp;
tmp2.cur=tx*3+ty;
swap(tmp2.s[tmp.cur],tmp2.s[tmp2.cur]);
tmp2.n=cantor(tmp2.s);
tmp2.deep=tmp.deep+1;
if(vis1[tmp2.n]){
reverse(path[tmp.n].begin(),path[tmp.n].end());
cout<<path[tmp2.n]<<dr2[p]<<path[tmp.n]<<endl;
return;
}
if(vis2[tmp2.n]) continue;
vis2[tmp2.n]=1;
path[tmp2.n]=path[tmp.n];
path[tmp2.n]+=dr2[p];
qq.push(tmp2);
}
}
L++;//层次+1
}
}
int main(){
char ch;
while(cin>>ch){
if(ch=='x') {
ch='0';
o.cur=0;
}
o.s[0]=ch-'0';
for(int i=1;i<9;i++){
cin>>ch;
if(ch=='x') {
ch='0';
o.cur=i;
}
o.s[i]=ch-'0';
}
o.deep=0;o.n=cantor(o.s);
int cnt=0;
for(int i=0;i<8;i++)//记录逆序数
if(o.s[i])
for(int j=i+1;j<9;j++)
if(o.s[j]<o.s[i] && o.s[j]) cnt++;
if(cnt&1) cout<<"unsolvable\n";
else bfs();
}
return 0;
}