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问题，可以用“康托展开”判重。那什么事康托展开呢？
    康托展开是一种特殊的哈希函数，针对八数码问题，康托展开完成了如表所示的工作。

状态	012345678	012345687	0123456768	......	876543210
Cantor	0	1	2	......	362880-1

    函数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] = {  };  //判断改装备是否被访问过

long int factory[] = { ,,,,,,,,, };//阶乘数

bool Cantor(int str[], int n)

{

    long result = ;

    for (int i = ; i < n; i++)

    {

        int counted = ;

        for (int j = i + ; j < n; j++)

        {

            if (str[i] > str[j])

                ++counted;

        }

        result += counted * factory[n - i - ];

    }

    if (!visited[result])

    {

        visited[result] = ;

        return ;

    }

    else return ;

}

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

AC代码：

 #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 = ;

 const int inf = 0x3f3f3f3f;

 struct node

 {

     int state[];

     int dis;

     string ans;

 };

 int dir[][] = { {-,},{,-},{,},{,} };

 char turn[] = { 'l','u','r','d' };

 int visited[maxn] = {  };

 int start[];

 int goal[] = {,,,,,,,,};

 long int factory[] = { ,,,,,,,,, };

 bool Cantor(int str[], int n)

 {

     long result = ;

     for (int i = ; i < n; i++)

     {

         int counted = ;

         for (int j = i + ; j < n; j++)

         {

             if (str[i] > str[j])

                 ++counted;

         }

         result += counted * factory[n - i - ];

     }

     if (!visited[result])

     {

         visited[result] = ;

         return ;

     }

     else return ;

 }

 bool check(int x, int y)

 {

     if (x >=  && x <  && y >=  && y < )

         return true;

     else return false;

 }

 queue<char>ans;

 int bfs()

 {

     node head;

     memcpy(head.state, start, sizeof(head.state));

     head.dis = ;

     queue<node>q;

     Cantor(head.state, );

     q.push(head);

     while (!q.empty())

     {

         head = q.front();

         q.pop();

         int z;

         for (z = ; z < ; z++)

         {

             if (head.state[z] == )

                 break;

         }

         int x = z % ;

         int y = z / ;

         for (int i = ; i < ; i++)

         {

             int newx = x + dir[i][];

             int newy = y + dir[i][];

             int nz = newx +  * 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)) == )

                 {

                     newnode.ans = newnode.ans + turn[i];

                     cout << newnode.ans << endl;

                     return newnode.dis;

                 }

                 if (Cantor(newnode.state, ))

                 {

                     newnode.ans = head.ans + turn[i];

                     q.push(newnode);

                 }

             }

         }

     }

     return -;

 }

 int main()

 {

     char s[];

     cin.getline(s, );

     int pos = ;

     for (int i = ; s[i] != '\0'; i++)

     {

         if (s[i] == ' ') continue;

         else if (s[i] == 'x') start[pos++] = ;

         else start[pos++] = s[i] - '';

     }

     int num = bfs();

     //printf("%d\n", num);

     if (num == -) printf("unsolvable\n");

     return ;

 }

巴特西

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

最新文章

热门文章