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！(ง •̀_•́)ง

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <string>
  4 #include <queue>
  5 #include <iostream>
  6 #include <algorithm>
  7 using namespace std;
  8 
  9 #define maxn 370000
 10 struct node
 11 {
 12     string path;//路径
 13     int s[10];  //state
 14     int loc;    //9的位置
 15     int ct;     //康拓hash
 16 };
 17 int fac[10] = {1, 1, 2, 6, 24, 120, 720, 720*7, 720*7*8, 720*7*8*9};
 18 //0!,1!,2!....9!
 19 int dir[4][2] = {0,1, 0,-1, -1,0, 1,0}; // r, l, u, d
 20 int vis[maxn];
 21 char di[5] = "lrdu"; //l, r, d, u
 22 string path[maxn];
 23 void init ()
 24 {
 25     memset (vis, 0, sizeof(vis));
 26 }
 27 
 28 int cantor (int a[]) //康拓hash
 29 {
 30     int sum = 0;
 31     for (int i=0; i<9; i++)
 32     {
 33         int m = 0;
 34         for (int j=i+1; j<9; j++)
 35             if (a[j] < a[i])
 36                 m ++;
 37             sum += m * (fac[9-i-1]);
 38     }
 39     return sum + 1;
 40 }
 41 
 42 void bfs ()
 43 {
 44     node cur, next;
 45     queue <node> Q;
 46 
 47     for(int i=0; i<8; i++)
 48         cur.s[i] = i + 1;
 49     cur.s[8] = 0;
 50     cur.ct = cantor (cur.s);
 51     cur.loc = 8;
 52 
 53     Q.push (cur);
 54     vis[cur.ct] = 1;
 55     path[cur.ct] = "";
 56 
 57     while (!Q.empty())
 58     {
 59         cur = Q.front();
 60         Q.pop ();
 61 
 62         for (int i=0; i<4; i++)
 63         {
 64             int x = cur.loc / 3 + dir[i][0];
 65             int y = cur.loc % 3 + dir[i][1];
 66             if (x<0 || x>2 || y<0 || y>2)
 67                 continue;
 68             next = cur;
 69             next.loc = x * 3 + y;
 70             next.s[cur.loc] = next.s[next.loc];
 71             next.s[next.loc] = 0;
 72             next.ct = cantor (next.s);
 73             if (!vis[next.ct])
 74             {
 75                 vis[next.ct] = 1;
 76                 path[next.ct] = di[i] + path[cur.ct];
 77                 Q.push (next);
 78             }
 79         }
 80     }
 81 
 82 }
 83 
 84 int main ()
 85 {
 86     init ();
 87     bfs ();
 88     char s[2];
 89     int a[10];
 90 
 91     while (scanf ("%s", s) != EOF)
 92     {
 93         if (s[0] == 'x')
 94             a[0] = 0;
 95         else
 96             a[0] = s[0] - '0';
 97 
 98         for (int i=1; i<9; i++)
 99         {
100             scanf ("%s", s);
101             if (s[0] == 'x')
102                 a[i] = 0;
103             else
104                 a[i] = s[0] - '0';
105         }
106         int m = cantor (a);
107         if (vis[m])
108             cout<<path[m]<<endl;
109         else
110             puts ("unsolvable");
111     }
112     return 0;
113 }