---

题目

描述
在一个3*3的九宫格棋盘里，放有8个数码，数码的数字分别是1~8。棋盘中还有一个位置是空着的，用0表示。可以通过在九宫格里平移数码来改变状态(即空格位在九宫格内能上下左右移动)。数码在任何情况下都不能离开棋盘。给出8个数码的初始状态（没放数码的空格用0表示）和目标状态，问从初始状态到目标状态，最少需要经过多少次移动操作。 例如 初始状态为：
$$\begin{array}{ccc}2& 6& 4\\ 1& 3& 7\\ 0& 5& 8\end{array}$$
目标状态为：
$$\begin{array}{ccc}8& 1& 5\\ 7& 3& 6\\ 4& 0& 2\end{array}$$
输入
两行 第一行9个数字，用空格隔开，表示初始状态 第二行9个数字，用空格隔开，表示目标状态
输出
一个数，即最短路径，如果没有答案，则输出-1
样例输入
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
样例输出
31

思路

此题要用康拓展开
康托展开

D_B解法（double_BFS）

显然，题目把初始状态和目标状态都告诉了你，典型的双B啊，注意一下空位的移动方式和移动之后的图的状态

代码

#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;

struct node{
    
    int step;
    int a[12], area[4][4];
    int flag;
    int xx, yy, c;
}A, B;

queue<node>G;

int dx[4] = {
    0, 0, 1, -1},
    dy[4] = {
    1, -1, 0, 0};

int v[2][362890], f[10] = {
    1,1,2,6,24,120,720,5040,40320,362880};

inline int contor(int *A){
    
    int sum = 0;
    for(int i = 0; i < 9 ; i ++){
    
        int x;
        x = 0;
        for(int j = i+1; j < 9; j ++){
    
            if( A[j] < A[i] )
                x++;
        }
        sum += f[8-i]*x;
    }
    return sum;
}

inline void Two_ways_BFS(){
    
    while( !G.empty() ){
    
        node t = G.front();
        G.pop();
        if( v[!t.flag][t.c] ){
    
            printf("%d\n",v[!t.flag][t.c]+t.step-2);
            return;
        }
        for(int i = 0; i < 4; i ++){
    
            int X = t.xx + dx[i];
            int Y = t.yy + dy[i];
            if( X < 0 || X > 2 || Y < 0 || Y > 2 )
                continue;
            node t1 = t;
            t1.xx = X, t1.yy = Y;
            t1.step++;
            swap(t1.area[X][Y], t1.area[t.xx][t.yy]);
            swap(t1.a[X*3+Y], t1.a[t.xx*3+t.yy]);
            t1.c = contor(t1.a);
            if( !v[t1.flag][t1.c] ){
    
                v[t1.flag][t1.c] = t1.step;
                G.push(t1);
            }
        }
    }
    printf("-1\n");
}

int main(){
    
    for(int i = 0; i < 3; i ++){
    
        for(int j = 0; j < 3; j ++){
    
            scanf("%d", &A.area[i][j]);
            A.a[i*3+j] = A.area[i][j];
            if( A.a[i*3+j] == 0 )
                A.xx = i, A.yy = j;
        }
    }
    A.c = contor(A.a);
    v[1][A.c] = 1;
    A.step = 1;
    A.flag = 1;
    for(int i = 0; i < 3; i ++){
    
        for(int j = 0; j < 3; j ++){
    
            scanf("%d", &B.area[i][j]);
            B.a[i*3+j] = B.area[i][j];
            if( B.a[i*3+j] == 0 )
                B.xx = i, B.yy = j;
        }
    }
    B.c = contor(B.a);
    v[0][B.c] = 1;
    B.step = 1;
    B.flag = 0;
    G.push(A);
    G.push(B);
    Two_ways_BFS();
    return 0;
}

A*

其实就是启发式函数不好写
我们定义不在目标位置的曼哈顿距离之和为h函数，因为0其实是空位，所以我们不考虑0，而我们其实是想要当前的F函数逼近目标的F函数，所以我们用优先队列存。
注意一下空位移动的边界和要求就行了

楼教主的光荣事迹

2006年第一届百度之星程序设计大赛决赛的最后一题，其实就是这道8数码难题。最终楼天城获得第一名。他是唯一一个采用A*算法AC这道题的选手，运行时间也是全场最快的，只用了0.0022s,排名第二的用的是双向BFS，用时0.0028s。

代码

#include <map>
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;

struct node{
    
    int step, IP_0, dif;
    int area[10];

    bool operator < (const node &b)const{
    
        if( dif+step > b.dif+b.step )
            return 1;
        return 0;
    }

}F, L;

priority_queue<node>G;

int tss;

int jc[10] = {
    1,1,2,6,24,120,720,5040,40320,362880};
int mu[10], dir[4] = {
    1, -1, 3, -3}, f[362900];

bool v[362900];

inline int abs(int x){
    
    return x > 0 ? x : -1*x;
}

inline int contor(int *x){
    
    int sum = 0;
    for(int i = 0; i < 9; i ++ ){
    
        int num = 0;
        for(int j = i+1; j < 9; j ++){
    
            if( x[i] > x[j] )
                num++;
        }
        sum += num*jc[8-i];
    }
    return sum;
}

inline int h_(node x){
    
    int sum = 0;
    for(int i = 0; i < 9; i ++){
    
        if( mu[i] != 0 ){
    
            for(int j = 0; j < 9; j ++){
    
                if( mu[i] == x.area[j] )
                    sum += abs(i/3-j/3)+abs(i-j)%3;
            }
        }
    }
    return sum;
}

inline void A_star(){
    
    F.dif = h_(F);
    for(F.IP_0 = 0; F.area[F.IP_0] != 0; F.IP_0++);
    G.push(F);
    int temp = contor(F.area);
    v[temp] = 1;
    f[temp] = F.step + F.dif;
    while( !G.empty() ){
    
        node t = G.top();
        G.pop();
        temp = contor(t.area);
        if( temp == tss ){
    
            printf("%d\n", t.step);
            return ;
        }
        for(int i = 0; i < 4; i ++){
    
            node t1 = t;
            t1.IP_0 = t.IP_0 + dir[i];
            if( t1.IP_0 < 9 && t1.IP_0 >= 0 ){
    
                if( t1.IP_0/3 == t.IP_0/3 || t1.IP_0%3 == t.IP_0%3 ){
    
                    swap(t1.area[t1.IP_0], t1.area[t.IP_0]);
                    temp = contor(t1.area);
                    if( !v[temp] ){
    
                        v[temp] = 1;
                        t1.dif = h_(t1);
                        t1.step++;
                        f[temp] = t1.step + t1.dif;
                        G.push(t1);
                    }
                }
            }
        }
    }
    printf("-1\n");
}

int main(){
    
    for(int i = 0; i < 9; i ++)
        scanf("%d", &F.area[i]);
    F.step = 0;
    for(int i = 0; i < 9; i ++){
    
        scanf("%d", &L.area[i]);
        mu[i] = L.area[i];
    }
    tss = contor(L.area);
    A_star();
    return 0;
}

优化

逆序对优化，我们可以把矩阵
$$\begin{array}{ccc}8& 1& 5\\ 7& 3& 6\\ 4& 0& 2\end{array}$$
转换为一个数组：
$81573642$
因为我们认为0为空位，所以左右交换不会改变原逆序对数量
而我们就需要探讨上下交换的情况
$$\begin{array}{ccc}{x}_1& x_2& x_3\\ x_4& 0& x_5\\ x_6& x_7& x_8\end{array}$$
1、$x_2>x_3$且$x_2>x_4$，逆序对数会+2
2、$x_2<x_3$且$x_2<x_4$，逆序对数会-2
3、$x_2<x_3$且$x_2>x_4$，逆序对数不变
所以不管怎么说，逆序对数的奇偶性不会发生变化
所以若目标状态和初始状态的逆序对数的奇偶性不同，那么一定没有解