【康托展开+状压BFS】poj1077 Eight(八数码问题)

这是经典的“八数码问题”。解法有很多，这里用的是状压BFS。

不过涉及一个有趣的东西：康托展开。

显然，我们可以把'x'当做0，这样每一个棋盘的状态对应的就是一个0~8的一个排列。

然后就是怎么压缩这个排列状态的问题。康托展开和其逆展开对此作了解答。

具体不难，就不介绍了。但是技不压身，我特地学习了一下，然后自己写了一个模板。就是一种编码方式，包括编码和解码，以后就可以直接用了。

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;

/*************************Cantor expansion***************************/
const int CACNTOR_MAX = 13;
int fac[CACNTOR_MAX] = {
	1, 1, 2, 6, 24, 120,
	720, 5040, 40320, 362880,
	3628800, 39916800, 479001600
}; //fac list, fac[i] = i!, fac[max] = fac[12] = 479 001 600

//put x = a[0] * 1! + ... + a[bit-1] * bit! and put into array a[]
//0 <= a[i] <= i+1
//x count from 0
int decode(int a[], int bit, int x) {
	bool tmp[CACNTOR_MAX] = {0};
	
	//array[1,2,...bit]
	//if U want to get [0, 1, ... , bit - 1]
	//change
	//a[i] = j
	//to: a[i] = j - 1;
	int res;
	for (int i = 0; i < bit; ++i) {
		a[i] = x / fac[bit - i - 1];
		x %= fac[bit - i - 1];
		int j = 1;
		for (int l = 0; l <= a[i]; ++j)
			if (!tmp[j]) ++l;
		tmp[--j] = true;
		a[i] = j - 1;
		if (j == 1) res = i;
	}
	return res;
}

//use [0, 1, 2, ..., bit-1] or [1, 2, ..., bit]
//it all works.
int encode(int a[], int bit) {
	int s = 0;
	for (int i = 0; i < bit; ++i) {
		int c = 0;
		for (int j = i + 1; j < bit; ++j) {
			c += a[j] < a[i];
		}
		s += c * fac[bit-i-1];
	}
	return s;
}
/********************************************************************/

const int MAX = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 + 7;
char move[MAX];
int father[MAX];
bool vis[MAX];

void debug(int status) {
	int a[10];
	decode(a, 9, status);
	for (int i = 0; i < 9; ++i) {
		printf("%d ", a[i]);
	}
	puts("");
}

int BFS(int s, int t) {
	memset(vis, false, sizeof(vis));
	memset(father, -1, sizeof(father));
	queue<int> Q;
	Q.push(s);
	vis[s] = true;

	int now, next, a[9];
	while (!Q.empty()) {
		now = Q.front();
		Q.pop();
		if (now == t) return t;
		
		int pos = decode(a, 9, now);
		
		//u: up
		if (pos > 2) {
			swap(a[pos], a[pos - 3]);
			next = encode(a, 9);
			if (!vis[next]) {
				vis[next] = true;
				father[next] = now;
				move[next] = 'u';
				Q.push(next);
				//debug(next);
			}
			swap(a[pos], a[pos - 3]);
		}
		
		//d
		if (pos < 6) {
			swap(a[pos], a[pos + 3]);
			next = encode(a, 9);
			if (!vis[next]) {
				vis[next] = true;
				father[next] = now;
				move[next] = 'd';
				Q.push(next);
				//debug(next);
			}
			swap(a[pos], a[pos + 3]);
		}
				
		//l
		if (pos % 3) {
			swap(a[pos], a[pos - 1]);
			next = encode(a, 9);
			if (!vis[next]) {
				vis[next] = true;
				father[next] = now;
				move[next] = 'l';
				Q.push(next);
				//debug(next);
			}
			swap(a[pos], a[pos - 1]);
		}

		//r
		if ((pos % 3) < 2) {
			swap(a[pos], a[pos + 1]);
			next = encode(a, 9);
			if (!vis[next]) {
				vis[next] = true;
				father[next] = now;
				move[next] = 'r';
				Q.push(next);
				//debug(next);
			}
			swap(a[pos], a[pos + 1]);
		}
	}
	return -1;
}

int main() {
	int a[10];
	char ch;
	while (~scanf(" %c", &ch)) {
		a[0] = ch == 'x' ? 0 : ch - '0';
		for (int i = 1; i < 9; ++i) {
			scanf(" %c", &ch);
			a[i] = ch == 'x' ? 0 : ch - '0';
		}
		int s = encode(a, 9);
		for (int i = 0; i < 9; ++i) {
			a[i] = (i + 1) % 9;
		}
		int t = encode(a, 9);
		int ret = BFS(s, t);
		if (ret == -1) {
			puts("unsolvable");
			continue;
		}
		//printf("s = %d, t = %d\n", s, t);

		int p = t;
		stack<char> S;
		while (!S.empty()) S.pop();
		while (p != -1) {
			S.push(move[p]);
			p = father[p];
		}
		S.pop();
		while (!S.empty()) {
			putchar(S.top());
			S.pop();
		}
		putchar('\n');
	}
	return 0;
}