HDU 1043 Eight（八数码）
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description - 题目描述
-puzzle有着超过100年的历史；就算没听过，估计也见过。它由15片滑块组成，各块标有数字1到15，并且全都装在一个4 x 4的边框里，防止哪块突然丢了。空块为’x’；这道题的目标是排列滑块使之顺序如下：
CN
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
唯一的合法操作是将’x’与其共边的滑块交换。例子如下，通过一系列移动解决一个被稍微打乱的问题。
CN
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8
9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12
13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x
r-> d-> r->
The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.
上一行的字母表示每次’x’与哪块相邻的滑块交换；有效值'r'，'l'，'u' 和 'd'分别表示右、左、上、下。 并非所有情况都有解；在1870年，一个叫Sam Loyd的人就以发布了一个无解版本而出名，成功地难住了许多人。实际上，要制造无解的情况只需交换两个滑块（当然是非’x’滑块）。 这个问题中，你需要写个程序解决著名的八数码问题，滑块为三行三列。
CN
You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
你会得到若干个八数码的配置描述。每个描述都是一个滑块初始位置的列表，从上往下，从左往右，使用数字1到8，还有’x’表示。比如， x 描述如下： x
CN
Output - 输出
如果无解，输出”unsolvable''”，否则输出一个仅由'r', 'l', 'u' 和 'd' 组成的字符串，描述求解的步骤。这个字符串不含空格且单独在一行。用例间别输出空行。
CN
Sample Input - 输入样例
2 3 4 1 5 x 7 6 8
Sample Output - 输出样例
ullddrurdllurdruldr
题解
逼你学新知识系列……（某废渣作死爆内存了……）
状态可以用全排列表示，用康托展开来压缩状态和去重，然后剩下的只有BFS了……（无聊用了树状数组求逆序数）
多组输入有点坑……其实如果符合情况直接输出空行也是可以的。
代码 C++
#include <cstdio>
#include <cstring>
#include <queue>
#define MX 362880
#define bitMX 10 int tre[bitMX];
int lowBit(int a) { return -a&a; }
void add(int i) {
while (i < bitMX) { ++tre[i]; i += lowBit(i); }
}
int sum(int i) {
int opt = ;
while (i) { opt += tre[i]; i -= lowBit(i); }
return opt;
} int ktf[], data[];
int preKte() {
int i, j, opt = ;
memset(tre, , sizeof tre);
for (i = ; ~i; --i) {
opt += sum(data[i])*ktf[i];
add(data[i]);
}
return opt;
}
void kte(int a) {
int i, j, tmp[];
for (i = ; i < ; ++i) tmp[i] = i + ;
for (i = ; i < ; ++i) {
j = a / ktf[i]; a %= ktf[i];
data[i] = tmp[j];
memcpy(tmp + j, tmp + j + , sizeof(int)*( - j));
}
data[i] = tmp[];
} int lst[MX];
char pre[MX];
void push(int now, int i, int j, char c, std::queue<int> &q) {
data[i] ^= data[j]; data[j] ^= data[i]; data[i] ^= data[j];
int nxt = preKte();
if (!pre[nxt]) {
lst[nxt] = now; pre[nxt] = c;
q.push(nxt);
}
data[i] ^= data[j]; data[j] ^= data[i]; data[i] ^= data[j];
}
void init() {
int i, j, now, nxt;
ktf[] = ;
for (i = , j = ; ~i; --i, ++j) ktf[i] = ktf[i + ] * j;
memset(lst, -, sizeof lst);
lst[] = ; pre[] = ' ';
std::queue<int> q; q.push();
while (!q.empty()) {
now = q.front(); q.pop();
kte(now);
for (i = ; data[i] != ; ++i);
if (i > ) push(now, i, i - , 'd', q);
if (i < ) push(now, i, i + , 'u', q);
if (i % ) push(now, i, i - , 'r', q);
if ((i + ) % ) push(now, i, i + , 'l', q);
} }
int main() {
init();
int i, j;
char red[];
while (gets(red)) {
for (i = j = ; i < ; i += , ++j) data[j] = red[i] == 'x' ? : red[i] - '';
if (~lst[i = preKte()]) {
for (j = i; j; j = lst[j]) putchar(pre[j]);
puts("");
}
else puts("unsolvable");
}
return ;
}