HDU 3567 Eight II（八数码 II）
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 130000/65536 K (Java/Others)
Problem Description - 题目描述
In this game, you are given a 3 by 3 board and 8 tiles. The tiles are numbered from 1 to 8 and each covers a grid. As you see, there is a blank grid which can be represented as an 'X'. Tiles in grids having a common edge with the blank grid can be moved into that blank grid. This operation leads to an exchange of 'X' with one tile.
We use the symbol 'r' to represent exchanging 'X' with the tile on its right side, and 'l' for the left side, 'u' for the one above it, 'd' for the one below it.
八数码，又名“九宫格”，其来源于一个古老的游戏。
此游戏中，给定3x3的底板与8个滑块。滑块数字为从1到8，且每个滑块覆盖一个格子。如你所见，这里有一个用’X’表示的空格。与空格拥有公共边的滑块可以移动到空格中。此操作会使’X’与滑块互换位置。
我们用’r’表示’X’和右边的滑块交换，’l’为左边，’u’为上边，’d’为下边。
A state of the board can be represented by a string S using the rule showed below.
每个起始状态可以用如下规则的字符串S表示。
The problem is to operate an operation list of 'r', 'u', 'l', 'd' to turn the state of the board from state A to state B. You are required to find the result which meets the following constrains:
1. It is of minimum length among all possible solutions.
2. It is the lexicographically smallest one of all solutions of minimum length.
这个问题需要使用操作'r'，'u'，'l'，'d' 使其从状态A到状态B。结果需符合如下要求： 1.所有解中长度最短的方案。 2.所有长度最短解中字典序最小的方案。
The first line is T (T <= 200), which means the number of test cases of this problem.
The input of each test case consists of two lines with state A occupying the first line and state B on the second line. It is guaranteed that there is an available solution from state A to B.
第一行为T(T <= 200)，表示测试用例的数量。 每个用例有两行，第一行为状态A，第二行为状态B。 状态A到B必定有解。
Output - 输出
The first line is in the format of "Case x: d", in which x is the case number counted from one, d is the minimum length of operation list you need to turn A to B. S is the operation list meeting the constraints and it should be showed on the second line.
每个测试用例输出两行。 第一行的格式为 "Case x: d"，x表示测试用例编号，从1开始，d表示从A到B操作列表的最短长度。 S为符合约束的操作列表，应放在第二行。
Sample Input - 输入样例
2 12X453786 12345678X 564178X23 7568X4123
Sample Output - 输出样例
Case 1: 2 dd Case 2: 8 urrulldr
题解
其他解法不明觉厉，就用了双向BFS。
和HDU 1043 Eight一个套路的康托展开，主要注意搜索的时候保障字典序最小，以及结束判断。
A方向的搜索才能结束全部的搜索状态，A方向优先距离，不考虑路径刷新。
B方向优先考虑距离，再考虑更低的字典序刷新路径。
水平差，代码渣……
代码 C++
1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <queue> 5 #define INF 0x7F7F7F7F 6 #define MX 362880 7 int tre[10], ftr[9], data[9], map[MX][4]; 8 bool isUS[MX]; 9 10 std::string a[94][94]; 11 12 int lowBit(int a) { return -a&a; } 13 void add(int i) { 14 while (i < 10) { ++tre[i]; i += lowBit(i); } 15 } 16 int sum(int i) { 17 int opt = 0; 18 while (i) { opt += tre[i]; i -= lowBit(i); } 19 return opt; 20 } 21 22 23 int pkt() { 24 int i, opt = 0; 25 memset(tre, 0, sizeof tre); 26 for (i = 8; ~i; --i) { 27 opt += sum(data[i])*ftr[i]; 28 add(data[i]); 29 } 30 return opt; 31 } 32 void kte(int a) { 33 int i, j, tmp[9]; 34 for (i = 0; i < 9; ++i) tmp[i] = i + 1; 35 for (i = 0; i < 8; ++i) { 36 j = a / ftr[i]; a %= ftr[i]; 37 data[i] = tmp[j]; 38 memcpy(tmp + j, tmp + j + 1, sizeof(int)*(8 - j)); 39 } 40 data[i] = tmp[0]; 41 } 42 43 void push(int now, int i, int j, int w, std::queue<int> &q) { 44 data[i] ^= data[j]; data[j] ^= data[i]; data[i] ^= data[j]; 45 int nxt = map[now][w] = pkt(); 46 data[i] ^= data[j]; data[j] ^= data[i]; data[i] ^= data[j]; 47 if (!isUS[nxt]) q.push(nxt); 48 isUS[nxt] = 1; 49 } 50 void init() {//d, l, r, u 51 int i, j, now; 52 ftr[7] = 1; 53 for (i = 6, j = 2; ~i; --i, ++j) ftr[i] = ftr[i + 1] * j; 54 memset(map, -1, sizeof map); 55 std::queue<int> q; 56 for (i = 0; i < MX; ++i) { 57 if (isUS[i]) continue; 58 q.push(i); isUS[i] = 1; 59 while (!q.empty()) { 60 now = q.front(); q.pop(); 61 kte(now); 62 for (j = 0; data[j] != 9; ++j); 63 if (j < 6) push(now, j, j + 3, 0, q); 64 if (j % 3) push(now, j, j - 1, 1, q); 65 if ((j + 1) % 3) push(now, j, j + 1, 2, q); 66 if (j > 2) push(now, j, j - 3, 3, q); 67 } 68 } 69 } 70 71 int len[MX][2], lst[MX][2], mid; 72 char pre[MX][2], car[4] = { 'd', 'l', 'r', 'u' }, opt[MX]; 73 void fPush(int now, int i, int w, std::queue<int> &q) { 74 if (mid != INF) return; 75 int nxt = map[now][i]; 76 if (nxt == -1) return; 77 char c = w ? car[3 - i] : car[i]; 78 if (w) { 79 if (len[nxt][0] != INF) return; 80 if (len[nxt][w] < len[now][w] + 1) return; 81 if (len[nxt][w] == len[now][w] + 1) { 82 if (c < pre[nxt][w]) { 83 pre[nxt][w] = c; 84 lst[nxt][w] = now; 85 } 86 return; 87 } 88 } 89 else { 90 if (len[nxt][w] <= len[now][w] + 1) return; 91 if (len[nxt][1] != INF) mid = nxt; 92 } 93 pre[nxt][w] = c; 94 len[nxt][w] = len[now][w] + 1; 95 lst[nxt][w] = now; 96 q.push(nxt); 97 } 98 void fid(int st, int ed) { 99 if (st == ed) puts("0"); 100 else { 101 int now, i, j; 102 memset(len, INF, sizeof len); memset(pre, 'z', sizeof pre); 103 len[st][0] = len[ed][1] = 0; 104 mid = INF; 105 std::queue<int> q; q.push(st); q.push(ed); 106 while (!q.empty()) { 107 if (mid != INF) break; 108 now = q.front(); q.pop(); 109 if (len[now][1] == INF) { 110 for (i = 0; i < 4; ++i) fPush(now, i, 0, q); 111 } 112 else if (len[now][0] == INF) { 113 for (i = 3; ~i; --i) fPush(now, i, 1, q); 114 } 115 else break; 116 } 117 now = mid; 118 printf("%d ", len[now][0] + len[now][1]); 119 for (i = now, j = 0; i != st; i = lst[i][0], ++j) opt[j] = pre[i][0]; 120 for (i = j - 1; ~i; --i) putchar(opt[i]); 121 for (i = now; i != ed; i = lst[i][1]) putchar(pre[i][1]); 122 123 } 124 puts(""); 125 } 126 int main() { 127 init(); 128 int t, i, j, st, ed; 129 char tmp[10]; 130 131 for (i = scanf("%d ", &t); i <= t; ++i) { 132 gets(tmp); 133 for (j = 0; j < 9; ++j) data[j] = tmp[j] == 'X' ? 9 : tmp[j] - '0'; 134 st = pkt(); 135 gets(tmp); 136 for (j = 0; j < 9; ++j) data[j] = tmp[j] == 'X' ? 9 : tmp[j] - '0'; 137 ed = pkt(); 138 printf("Case %d: ", i); 139 fid(st, ed); 140 } 141 return 0; 142 }