[HDOJ1043]Eight（康托展开 BFS 打表）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043

　　八数码问题，因为固定了位置所以以目标位置开始搜索，把所有情况（相当于一个排列）都记录下来，用康托展开来完成序列的记录问题开始BFS。打好表后按给出序列的康托数确定开始位置，逆向查找。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 typedef struct Node1 {
 23     char s;
 24     int pre;
 25     Node1() { pre = -1; }
 26 }Node1;
 27 typedef struct Node2 {
 28     int status[11];
 29     int n, son;
 30 }Node2;
 31 
 32 Node1 path[666666];
 33 int dx[4] = {1, -1, 0, 0};
 34 int dy[4] = {0, 0, 1, -1};
 35 int fac[11];
 36 
 37 void init() {
 38     fac[0] = fac[1] = 1;
 39     for(int i = 2; i <= 10; i++) {
 40         fac[i] = fac[i-1] * i;
 41     }
 42 }
 43 
 44 int ecantor(int* s, int n = 9) {
 45     int num = 0;
 46     for(int i = 0; i < n; i++) {
 47         int tmp = 0;
 48         for(int j = i + 1; j < n; j++) {
 49             if(s[j] < s[i]) {
 50                 tmp++;
 51             }
 52         }
 53         num += fac[n-1-i] * tmp;
 54     }
 55     return num;
 56 }
 57 
 58 void bfs() {
 59     queue<Node2> q;
 60     Node2 a, b;
 61     int t = 0;
 62     for(int i = 0; i < 9; i++) {
 63         a.status[i] = i + 1;
 64     }
 65     a.n = 8; a.son = 0;
 66     path[a.son].pre = 0;
 67     q.push(a);
 68     while(!q.empty()) {
 69         a = q.front(); q.pop();
 70         for(int i = 0; i < 4; i++) {
 71             b = a;
 72             int xx = a.n % 3 + dx[i];
 73             int yy = a.n / 3 + dy[i];
 74             if(!(xx >= 0 && xx < 3 && yy >= 0 && yy < 3)) continue;
 75             b.n = yy * 3 + xx;
 76             swap(b.status[b.n], b.status[a.n]);
 77             b.son = ecantor(b.status);
 78             if(path[b.son].pre == -1) {
 79                 path[b.son].pre = a.son;
 80                 if(i == 0) path[b.son].s = 'l';
 81                 if(i == 1) path[b.son].s = 'r';
 82                 if(i == 2) path[b.son].s = 'u';
 83                 if(i == 3) path[b.son].s = 'd';
 84                 q.push(b);
 85             }
 86         }
 87     }
 88 }
 89 
 90 int main() {
 91     // freopen("in", "r", stdin);
 92     init();
 93     int s, ss[11];
 94     char ch[55];
 95     bfs();
 96     while(gets(ch)) {
 97         int cnt = 0;
 98         for(int i = 0; ch[i]; i++) {
 99             if(ch[i] == 'x') {
100                 ss[cnt++] = 9;
101             }
102             else if(ch[i] >= '0' && ch[i] <= '9') {
103                 ss[cnt++] = ch[i] - '0';
104             }
105         }
106         s = ecantor(ss);
107         if(path[s].pre == -1) {
108             printf("unsolvable
");
109             continue;
110         }
111         while(s != 0) {
112             printf("%c", path[s].s);
113             s = path[s].pre;
114         }
115         printf("
");
116     }
117     return 0;
118 }