康托展开
定义
其中表示ai当前未出现的元素中是排第几个(从0开始)。并且0<=ai<i(1<=i<=n)。它的意义是把一个序列映射成一个数。（来自百度百科）
例如，有一个数组 s = ["A", "B", "C", "D"]，它的一个排列 s1 = ["D", "B", "A", "C"]，现在要把 s1 映射成 X。n 指的是数组的长度，也就是4，所以X(s1) = a4*3! + a3*2! + a2*1! + a1*0!
a4 = "D" 这个元素在子数组 ["D",
"B", "A", "C"] 中是第几大的元素。"A"是第0大的元素，"B"是第1大的元素，"C" 是第2大的元素，"D"是第3大的元素，所以 a4 = 3。
a3 = "B" 这个元素在子数组 ["B",
"A", "C"] 中是第几大的元素。"A"是第0大的元素，"B"是第1大的元素，"C" 是第2大的元素，所以 a3 = 1。
a2 = "A" 这个元素在子数组 ["A", "C"] 中是第几大的元素。"A"是第0大的元素，"C"是第1大的元素，所以 a2 =
0。
a1 = "C" 这个元素在子数组 ["C"] 中是第几大的元素。"C" 是第0大的元素，所以 a1 = 0。（因为子数组只有1个元素，所以a1总是为0）
所以，X(s1) = 3*3! + 1*2! + 0*1! + 0*0! = 20
如果已知 s = ["A", "B",
"C", "D"]，X(s1) = 20，利用下图的方式可以求出a1，a2，a3，a4，进而推出序列。（来源于http://blog.csdn.net/zhongkeli/article/details/6966805）
HDU 1043 Eight 是一个经典的八数码问题，对于任意给的一个状态，求出是否可以到达初始的状态，求出最小的步数。利用康托定理，将每个状态转换成一个数，从最终状态出发进行BFS，打表保存最后在做查询。注意点是这道题的输入有多组，不能scanf，用gets处理输入。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 370000; 4 int st[11]; 5 int fac[10]; 6 int dx[] = {0, 1, 0, -1}; 7 int dy[] = {1, 0, -1, 0}; 8 struct node1 { 9 int fa; 10 char ss; 11 } f[MAXN]; 12 struct node { 13 int loc, cat; 14 int ar[11]; 15 }u, v; 16 void get_fac() { 17 fac[0] = 1; 18 for (int i = 1; i < 9; i++) { 19 fac[i] = i*fac[i - 1]; 20 } 21 } 22 int cantor(int a[]) { 23 int res = 0; 24 for(int i = 0; i < 9; i++) { 25 int k = 0; 26 for(int j = i + 1; j < 9; j++) 27 if(a[i] > a[j]) k++; 28 res += k*fac[8 - i]; 29 } 30 return res; 31 } 32 void bfs() { 33 queue<node> que; 34 while (que.size()) que.pop(); 35 u.loc = 8; 36 for (int i = 0; i < 9; i++) u.ar[i] = i + 1; 37 u.cat = 0; 38 f[u.cat].fa = 0; 39 que.push(u); 40 while (que.size()) { 41 v = que.front(); que.pop(); 42 for (int i = 0; i < 4; i++) { 43 int tx = v.loc/3 + dx[i]; 44 int ty = v.loc%3 + dy[i]; 45 if (tx >= 3 || tx < 0 || ty >= 3 || ty < 0) continue; 46 u = v; u.loc = tx*3 + ty; 47 int temp = u.ar[v.loc]; 48 u.ar[v.loc] = u.ar[u.loc]; 49 u.ar[u.loc] = temp; 50 u.cat = cantor(u.ar); 51 if (f[u.cat].fa == -1) { 52 if (i == 0) f[u.cat].ss = 'l'; 53 else if (i == 1) f[u.cat].ss = 'u'; 54 else if (i == 2) f[u.cat].ss = 'r'; 55 else f[u.cat].ss = 'd'; 56 f[u.cat].fa = v.cat; 57 que.push(u); 58 } 59 } 60 } 61 } 62 void init() { 63 get_fac(); 64 for (int i = 0; i < MAXN; i++) f[i].fa = -1; 65 } 66 int main(int argc, char const *argv[]) { 67 init();bfs(); 68 char str[100]; 69 while (gets(str) > 0) { 70 int cnt = 0; 71 for (int i = 0; str[i] != ' ' ; i++) { 72 if (str[i] == 'x') st[cnt++] = 9; 73 else if (str[i] >= '0' && str[i] <= '9') st[cnt++] = str[i] - '0'; 74 } 75 int d = cantor(st); 76 if (f[d].fa == -1) printf("%s ", "unsolvable"); 77 else { 78 while (d) { 79 printf("%c", f[d].ss); 80 d = f[d].fa; 81 } 82 printf(" "); 83 } 84 } 85 86 return 0; 87 }
HDU 3567 EightII 是个稍微升级版的题目，一开始我直接BFS，结果超时。然后看到dalao打表X位于9个不同位置，然后每次将初始序列进行映射为九个中的一个，在把最终状态的序列按照同样的法则进行映射，真是膜拜了
1 #include <bits/stdc++.h> 2 #define LOCAL 3 using namespace std; 4 const int MAXN = 500000; 5 int fn[20], fac[20]; 6 int fa[10][MAXN], res[10][MAXN]; 7 int dx[] = {1,0,0,-1}; 8 int dy[] = {0,-1,1,0}; 9 char way[] = "dlru"; 10 bool vis[MAXN]; 11 char st[20], pt[MAXN]; 12 struct node { 13 char ss[10]; 14 int loc; 15 }tp; 16 int cantor(char s[]) { 17 int res = 0; 18 for (int i = 0; i < 9; i++) { 19 int k = 0; 20 for (int j = i + 1; j < 9; j++) { 21 if (s[i] > s[j]) k++; 22 } 23 res += fac[8 - i]*k; 24 } 25 return res; 26 } 27 void bfs(int p) { 28 queue<node> que; 29 memset(fa[p], -1, sizeof(fa[p])); 30 memset(vis, false, sizeof(vis)); 31 strcpy(tp.ss, st); int tpcat = cantor(tp.ss); 32 tp.loc = p; vis[tpcat] = true; 33 que.push(tp); 34 node u, v; 35 while (!que.empty()) { 36 v = que.front(); que.pop(); 37 int vcat = cantor(v.ss); 38 for (int i = 0; i < 4; i++) { 39 u = v; 40 int tx = u.loc/3 + dx[i]; 41 int ty = u.loc%3 + dy[i]; 42 if (tx > 2 || tx < 0 || ty > 2 || ty < 0) continue; 43 u.loc = tx*3 + ty; 44 u.ss[v.loc] = u.ss[u.loc]; u.ss[u.loc] = 'X'; 45 int ucat = cantor(u.ss); 46 if (vis[ucat]) continue; 47 vis[ucat] = true; 48 res[p][ucat] = way[i]; 49 fa[p][ucat] = vcat; 50 que.push(u); 51 } 52 } 53 } 54 void init() { 55 fac[0] = 1; 56 for (int i = 1; i < 10; i++) { 57 fac[i] = fac[i - 1]*i; 58 } 59 memset(fa, -1, sizeof(fa)); 60 strcpy(st, "X12345678"); bfs(0); 61 strcpy(st, "1X2345678"); bfs(1); 62 strcpy(st, "12X345678"); bfs(2); 63 strcpy(st, "123X45678"); bfs(3); 64 strcpy(st, "1234X5678"); bfs(4); 65 strcpy(st, "12345X678"); bfs(5); 66 strcpy(st, "123456X78"); bfs(6); 67 strcpy(st, "1234567X8"); bfs(7); 68 strcpy(st, "12345678X"); bfs(8); 69 } 70 int main(int argc, char const *argv[]) 71 { 72 int T; 73 // freopen("in.txt", "r", stdin); 74 // freopen("out1.txt", "w", stdout); 75 init(); 76 int Kcase = 0; 77 scanf("%d", &T); 78 while (T--) { 79 int cnt = 0; int p; 80 char str[100]; scanf("%s", str); 81 for (int i = 0; i < 9; i++) { 82 if (str[i] == 'X') p = i; 83 else fn[str[i] - '0'] = cnt++; 84 } 85 scanf("%s", str); cnt = 0; 86 for (int i = 0; i < 9; i++) { 87 if (str[i] != 'X') str[i] = fn[str[i] - '0'] + '1'; 88 } 89 int d = cantor(str); 90 while (d != -1) { 91 pt[cnt++] = res[p][d]; 92 d = fa[p][d]; 93 } 94 printf("Case %d: %d ", ++Kcase, cnt-1); 95 for (int i = cnt - 2; i >= 0; i--) { 96 printf("%c", pt[i]); 97 } 98 printf(" "); 99 } 100 return 0; 101 }