POJ 1077 Eight （BFS+康托展开）详解

本题知识点和基本代码来自《算法竞赛 入门到进阶》（作者：罗勇军 郭卫斌）

如有问题欢迎巨巨们提出

题意：八数码问题是在一个3*3的棋盘上放置编号为1~8的方块，其中有一块为控制，与空格相邻的数字方块可以移动到空格里。我们要求指定初始棋盘和目标棋盘，计算出最少移动次数，同时要输出数码的移动数列。初始棋盘样例已给出，目标棋盘为“1 2 3 4 5 6 7 8 x”

输入：

 2  3  4  1  5  x  7  6  8 

输出：

ullddrurdllurdruldr 详解：  八数码是经典的BFS问题，可以用“康托展开”判重。那什么事康托展开呢？  康托展开是一种特殊的哈希函数，针对八数码问题，康托展开完成了如表所示的工作。

 函数Cantor（）实现的功能是：输入一个排序，即第一行的某个排序，计算它的Cantor值，即第二行的数。Cantor的时间复杂度为O(n*n)，n是集合中元素的个数，利用CANTOR展开可以实现八数码的快速判重。  距离康托展开的实现原理：  例：判断2143是{1,2,3,4}的全排列中第几大的数。
    计算排在2143前面的排列数目，可以转换成以下排列的和：
   （1）首位小于2的所有排序，比2小的只有一个数，后面三个数的排序有3!个。
   （2）首位为2，第2位小于1的所有排序，无，写成0*2!=0.
   （3）前两位为21，第三位小于4的数，即2134，写成1*1！=1.  (4)前三位为214，第四位小于3的数，无，即0*0！=1.
    sum=8.即2143是第八大的数。
    
　　把一个集合产生的全排列按字典序排序，第X个排序的计算公式如下：
　　X=a[n]*(n-1)!+a[n-1]*(n-2)!+....+a[i]*(i-1)!+...+a[2]*1!+a[1]*0![1].其中，a[i]为当前未出现的元素排在第几个。（从0开始）0<=a[i]<i.

康托展开的基础代码： 

int visited[maxn] = { 0 };  //判断改装备是否被访问过
long int factory[] = { 1,1,2,6,24,120,720,5040,40320,362880 };//阶乘数

bool Cantor(int str[], int n)
{
    long result = 0;
    for (int i = 0; i < n; i++)
    {
        int counted = 0;
        for (int j = i + 1; j < n; j++)
        {
            if (str[i] > str[j])
                ++counted;
        }
        result += counted * factory[n - i - 1];
    }
    if (!visited[result])
    {
        visited[result] = 1;
        return 1;
    }
    else return 0;
}

这道题看了很多博客，存步骤的答案方式很多，我是在结构体里设置string，然后在bfs过程中逐步保存步骤，最后输出达到最终状态的答案。看代码应该能理解。还有保存图的时候要注意，样例里空格不止一个，所以灵活点保存。我最后时间跑出来是750ms，比较慢，可用其他搜索方法优化。

#pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<string>
#include<map>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
#define mm(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int maxn = 362880;
const int inf = 0x3f3f3f3f;

struct node
{
    int state[9];
    int dis;
    string ans;
};

int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };
char turn[4] = { 'l','u','r','d' };
int visited[maxn] = { 0 };
int start[9];
int goal[9] = {1,2,3,4,5,6,7,8,0};

long int factory[] = { 1,1,2,6,24,120,720,5040,40320,362880 };

bool Cantor(int str[], int n)
{
    long result = 0;
    for (int i = 0; i < n; i++)
    {
        int counted = 0;
        for (int j = i + 1; j < n; j++)
        {
            if (str[i] > str[j])
                ++counted;
        }
        result += counted * factory[n - i - 1];
    }
    if (!visited[result])
    {
        visited[result] = 1;
        return 1;
    }
    else return 0;
}

bool check(int x, int y)
{
    if (x >= 0 && x < 3 && y >= 0 && y < 3)
        return true;
    else return false;
}

queue<char>ans;

int bfs()
{
    node head;
    memcpy(head.state, start, sizeof(head.state));
    head.dis = 0;
    queue<node>q;
    Cantor(head.state, 9);
    q.push(head);
    while (!q.empty())
    {
        head = q.front();
        q.pop();
        int z;
        for (z = 0; z < 9; z++)
        {
            if (head.state[z] == 0)
                break;
        }
        int x = z % 3;
        int y = z / 3;
        for (int i = 0; i < 4; i++)
        {
            int newx = x + dir[i][0];
            int newy = y + dir[i][1];
            int nz = newx + 3 * newy;
            if (check(newx, newy))
            {
                node newnode = head;
                swap(newnode.state[z], newnode.state[nz]); //0的交换
                newnode.dis++;
                if (memcmp(newnode.state, goal, sizeof(goal)) == 0)
                {
                    newnode.ans = newnode.ans + turn[i];
                    cout << newnode.ans << endl;
                    return newnode.dis;
                }
                if (Cantor(newnode.state, 9))
                {
                    newnode.ans = head.ans + turn[i];
                    q.push(newnode);
                }
            }
        }
    }
    return -1;
}

int main()
{
    char s[100];
    cin.getline(s, 100);
    int pos = 0;
    for (int i = 0; s[i] != '\0'; i++)
    {
        if (s[i] == ' ') continue;
        else if (s[i] == 'x') start[pos++] = 0;
        else start[pos++] = s[i] - '0';
    }
    int num = bfs();
    //printf("%d\n", num);
    if (num == -1) printf("unsolvable\n");
    return 0;
}