Hdu 1043 Eight (八数码问题)

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=1043

题目描述：

　　3*3的格子，填有1到8,8个数字，还有一个x，x可以上下左右移动，问最终能否移动到12345678x的状态？

　　hint:每一个3*3的格子从上到右，从左到右，一行一行读。

解题思路：

　　比较简单的八数码问题，大一暑假老师讲过，一直手懒脑懒并没有亲自尝试过。因为是多实例，先从12345678x的状态bfs出来所有可以到达的状态，并且记录下来路径。八数码最重要的就是保存状态，如果这个题目用十进制保存状态的话，至少要到达10^9的数量级。可以利用康拓展开hash搜索到的状态，空间可以缩小到9！(ง •̀_•́)ง

 #include <stdio.h>

 #include <string.h>

 #include <string>

 #include <queue>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define maxn 370000

 struct node

 {

     string path;//路径

     int s[];  //state

     int loc;    //9的位置

     int ct;     //康拓hash

 };

 int fac[] = {, , , , , , , *, **, ***};

 //0!,1!,2!....9!

 int dir[][] = {,, ,-, -,, ,}; // r, l, u, d

 int vis[maxn];

 char di[] = "lrdu"; //l, r, d, u

 string path[maxn];

 void init ()

 {

     memset (vis, , sizeof(vis));

 }

 int cantor (int a[]) //康拓hash

 {

     int sum = ;

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

     {

         int m = ;

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

             if (a[j] < a[i])

                 m ++;

             sum += m * (fac[-i-]);

     }

     return sum + ;

 }

 void bfs ()

 {

     node cur, next;

     queue <node> Q;

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

         cur.s[i] = i + ;

     cur.s[] = ;

     cur.ct = cantor (cur.s);

     cur.loc = ;

     Q.push (cur);

     vis[cur.ct] = ;

     path[cur.ct] = "";

     while (!Q.empty())

     {

         cur = Q.front();

         Q.pop ();

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

         {

             int x = cur.loc /  + dir[i][];

             int y = cur.loc %  + dir[i][];

             if (x< || x> || y< || y>)

                 continue;

             next = cur;

             next.loc = x *  + y;

             next.s[cur.loc] = next.s[next.loc];

             next.s[next.loc] = ;

             next.ct = cantor (next.s);

             if (!vis[next.ct])

             {

                 vis[next.ct] = ;

                 path[next.ct] = di[i] + path[cur.ct];

                 Q.push (next);

             }

         }

     }

 }

 int main ()

 {

     init ();

     bfs ();

     char s[];

     int a[];

     while (scanf ("%s", s) != EOF)

     {

         if (s[] == 'x')

             a[] = ;

         else

             a[] = s[] - '';

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

         {

             scanf ("%s", s);

             if (s[] == 'x')

                 a[i] = ;

             else

                 a[i] = s[] - '';

         }

         int m = cantor (a);

         if (vis[m])

             cout<<path[m]<<endl;

         else

             puts ("unsolvable");

     }

     return ;

 }