http://acm.hdu.edu.cn/showproblem.php?pid=4531

main.cpp

#include <cstdio>
#include <cstring>
#include <queue>

#define N 9
#define set1(a, b) a = ((a) | (1 << (b)))
#define set0(a, b) a = ((a) & (~(1 << (b))))
#define get(a, b) (((a) >> (b)) & 1)
#define fetch(a, b) ((((a) >> (2 * (b))) & 1) + (((a) >> (2 * (b))) & 2))
#define movable(p) ((((a[p]) >> 8) & 1) == 0)

using namespace std;

bool hash[400000];
unsigned int a[N];
int colorN;
bool g[N][N][4];
bool vis[3][3][4];

void dfs(const int p[3][3], int i, int j, int k) {
	static int dirx[] = {-1, 1, 0, 0};
	static int diry[] = {0, 0, -1, 1};
	if (vis[i][j][k]) {
		return;
	}
	vis[i][j][k] = true;
	for (int kk = 0; kk < 4; kk++) {
		if (k / 2 != kk / 2 && fetch(a[p[i][j]], k) == fetch(a[p[i][j]], kk)) {
			dfs(p, i, j, kk);
		}
	}
	int ii = i + dirx[k];
	int jj = j + diry[k];
	static int oppo[] = {1, 0, 3, 2};
	if (0 <= ii && ii < 3 && 0 <= jj && jj < 3) {
		int kk = oppo[k];
		int d = k;
		int l = p[i][j], r = p[ii][jj];
		if (l > r) {
			int temp = l;
			l = r;
			r = temp;
			d = oppo[k];
		}
		if (g[l][r][d]) {
			dfs(p, ii, jj, kk);
		}
	}
}

unsigned int enco(int p[9]);
bool succ(const int p[3][3]) {
	int cnt = 0;
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 4; k++) {
				if (!vis[i][j][k]) {
					cnt++;
					dfs(p, i, j, k);
				}
			}
		}
	}
	return cnt == colorN;
}

void push(queue<pair<unsigned int, int> > & q, pair<unsigned int, int> item) {
	if (!hash[item.first]) {
		hash[item.first] = true;
		q.push(item);
	}
}

pair<unsigned int, int> pop(queue<pair<unsigned int, int> > & q) {
	pair<unsigned int, int> ret = q.front();
	q.pop();
	return ret;
}

int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};

unsigned int enco(int p[9]) {
	unsigned int num = 0;
	for (int i = 0; i < 9; i++) {
		int tmp = 0;
		for (int j = i + 1; j < 9; j++) {
			if (p[j] < p[i]) {
				tmp++;
			}
		}
		num += fac[9 - i - 1] * tmp;
	}
	return num;
}

void deco(int res[9], unsigned int x) {
	int i, j, l, t;
	static bool h[12];
	memset(h, 0, sizeof(h));
	for (i = 1; i <= 9; i++) {
		t = x / fac[9 - i];
		x -= t * fac[9 - i];
		for (j = 1, l = 0; l <= t; j++) {
			if (!h[j]) {
				l++;
			}
		}
		j--;
		h[j] = true;
		res[i - 1] = j - 1;
	}
}

int main() {
	int T;
	scanf("%d", &T);
	getchar();
	for (int ca = 1; ca <= T; ca++) {
		memset(a, 0, sizeof(a));
		int colorH[] = {0,0,0,0};
		for (int i = 0; i < N; i++) {
			char ch;
			for (int j = 0; j < 4; j++) {
				ch = getchar();
				if (ch == 'R') {
					set0(a[i], 2 * j);
					set0(a[i], 2 * j + 1);
					colorH[0] = 1;
				} else if (ch == 'G') {
					set1(a[i], 2 * j);
					set0(a[i], 2 * j + 1);
					colorH[1] = 1;
				} else if (ch == 'B') {
					set0(a[i], 2 * j);
					set1(a[i], 2 * j + 1);
					colorH[2] = 1;
				} else if (ch == 'O') {
					set1(a[i], 2 * j);
					set1(a[i], 2 * j + 1);
					colorH[3] = 1;
				}
			}
			if (getchar() == '1') {
				set1(a[i], N - 1);
			} else {
				set0(a[i], N - 1);
			}
			getchar();
		}
		colorN = 0;
		for (int i = 0; i < 4; i++) {
			colorN += colorH[i];
		}
		memset(g, 0, sizeof(g));
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				g[i][j][0] = (fetch(a[i], 0) == fetch(a[j], 1));
				g[i][j][1] = (fetch(a[i], 1) == fetch(a[j], 0));
				g[i][j][2] = (fetch(a[i], 2) == fetch(a[j], 3));
				g[i][j][3] = (fetch(a[i], 3) == fetch(a[j], 2));
			}
		}

		memset(hash, 0, sizeof(hash));
		queue<pair<unsigned int, int> > q;
		push(q, make_pair(0, 0));
		while (!q.empty()) {
			pair<unsigned int, int> u = pop(q);
			int p[3][3];
			deco((int *)p, u.first);
			int temp;
			for (int i = 0; i < 3; i++) {
				if (movable(p[i][0]) && movable(p[i][1]) && movable(p[i][2])) {
					temp = p[i][0];
					p[i][0] = p[i][1];
					p[i][1] = p[i][2];
					p[i][2] = temp;
					if (succ(p)) {
						printf("Case #%d: %d\n", ca, u.second + 1);
						goto out;
					} else {
						unsigned v = enco((int *)p);
						push(q, make_pair(v, u.second + 1));
					}
					temp = p[i][2];
					p[i][2] = p[i][1];
					p[i][1] = p[i][0];
					p[i][0] = temp;

					temp = p[i][2];
					p[i][2] = p[i][1];
					p[i][1] = p[i][0];
					p[i][0] = temp;
					if (succ(p)) {
						printf("Case #%d: %d\n", ca, u.second + 1);
						goto out;
					} else {
						unsigned v = enco((int *)p);
						push(q, make_pair(v, u.second + 1));
					}
					temp = p[i][0];
					p[i][0] = p[i][1];
					p[i][1] = p[i][2];
					p[i][2] = temp;
				}
			}
			for (int j = 0; j < 3; j++) {
				if (movable(p[0][j]) && movable(p[1][j]) && movable(p[2][j])) {
					temp = p[0][j];
					p[0][j] = p[1][j];
					p[1][j] = p[2][j];
					p[2][j] = temp;
					if (succ(p)) {
						printf("Case #%d: %d\n", ca, u.second + 1);
						goto out;
					} else {
						unsigned v = enco((int *)p);
						push(q, make_pair(v, u.second + 1));
					}
					temp = p[2][j];
					p[2][j] = p[1][j];
					p[1][j] = p[0][j];
					p[0][j] = temp;

					temp = p[2][j];
					p[2][j] = p[1][j];
					p[1][j] = p[0][j];
					p[0][j] = temp;
					if (succ(p)) {
						printf("Case #%d: %d\n", ca, u.second + 1);
						goto out;
					} else {
						unsigned v = enco((int *)p);
						push(q, make_pair(v, u.second + 1));
					}
					temp = p[0][j];
					p[0][j] = p[1][j];
					p[1][j] = p[2][j];
					p[2][j] = temp;
				}
			}
		}
out:
		continue;
	}
	return 0;
}