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

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

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

 #include <algorithm>

 #include <iostream>

 #include <iomanip>

 #include <cstring>

 #include <climits>

 #include <complex>

 #include <fstream>

 #include <cassert>

 #include <cstdio>

 #include <bitset>

 #include <vector>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <ctime>

 #include <set>

 #include <map>

 #include <cmath>

 using namespace std;

 typedef struct Node1 {

     char s;

     int pre;

     Node1() { pre = -; }

 }Node1;

 typedef struct Node2 {

     int status[];

     int n, son;

 }Node2;

 Node1 path[];

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

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

 int fac[];

 void init() {

     fac[] = fac[] = ;

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

         fac[i] = fac[i-] * i;

     }

 }

 int ecantor(int* s, int n = ) {

     int num = ;

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

         int tmp = ;

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

             if(s[j] < s[i]) {

                 tmp++;

             }

         }

         num += fac[n--i] * tmp;

     }

     return num;

 }

 void bfs() {

     queue<Node2> q;

     Node2 a, b;

     int t = ;

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

         a.status[i] = i + ;

     }

     a.n = ; a.son = ;

     path[a.son].pre = ;

     q.push(a);

     while(!q.empty()) {

         a = q.front(); q.pop();

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

             b = a;

             int xx = a.n %  + dx[i];

             int yy = a.n /  + dy[i];

             if(!(xx >=  && xx <  && yy >=  && yy < )) continue;

             b.n = yy *  + xx;

             swap(b.status[b.n], b.status[a.n]);

             b.son = ecantor(b.status);

             if(path[b.son].pre == -) {

                 path[b.son].pre = a.son;

                 if(i == ) path[b.son].s = 'l';

                 if(i == ) path[b.son].s = 'r';

                 if(i == ) path[b.son].s = 'u';

                 if(i == ) path[b.son].s = 'd';

                 q.push(b);

             }

         }

     }

 }

 int main() {

     // freopen("in", "r", stdin);

     init();

     int s, ss[];

     char ch[];

     bfs();

     while(gets(ch)) {

         int cnt = ;

         for(int i = ; ch[i]; i++) {

             if(ch[i] == 'x') {

                 ss[cnt++] = ;

             }

             else if(ch[i] >= '' && ch[i] <= '') {

                 ss[cnt++] = ch[i] - '';

             }

         }

         s = ecantor(ss);

         if(path[s].pre == -) {

             printf("unsolvable\n");

             continue;

         }

         while(s != ) {

             printf("%c", path[s].s);

             s = path[s].pre;

         }

         printf("\n");

     }

     return ;

 }