【魔板】 （C语言代码）

解题思路: 

    bfs + 康托展开

注意事项:

    记得输入魔板序列是顺时针表示的- -，要转换一下

参考代码:

#include<stdio.h>
#include<string.h>

#define MAXN 40330 // 8! + 10
#define MAXL 8

struct {
	char str[MAXL + 1];
	char opt;
	int par;
} queue[MAXN], tmp, nxt;

int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040 };
int vis[MAXN];
char opt[] = "ABC";
char aim[MAXL + 1];
void(*fun[3])(char *str);

int hash(char *str) {

	int i, j, cnt, sum = 0;

	for (i = 0; i < MAXL; ++i) {

		for (cnt = 0, j = i + 1; j < MAXL; ++j) {

			if (str[j] > str[i]) ++cnt;
		}
		sum += cnt * fac[MAXL - i - 1];
	}

	if (vis[sum]) return 1;
	
	vis[sum] = 1;
	return 0;
}

void swap(char *a, char *b) {

	char tmp = *a;
	*a = *b;
	*b = tmp;
}

void optA(char *str) {

	swap(&str[0], &str[4]);
	swap(&str[1], &str[5]);
	swap(&str[2], &str[6]);
	swap(&str[3], &str[7]);
}

void optB(char *str) {

	int i;
	char tmp;

	for (tmp = str[3], i = 3; i > 0; --i) {

		str[i] = str[i - 1];
	}
	str[0] = tmp;

	for (tmp = str[7], i = 7; i > 4; --i) {

		str[i] = str[i - 1];
	}
	str[4] = tmp;
}

void optC(char *str) {

	char tmp = str[1];
	str[1] = str[5];
	str[5] = str[6];
	str[6] = str[2];
	str[2] = tmp;
}

void print(int k) {

	if (queue[k].par == -1) return;
	print(queue[k].par);
	printf("%c", queue[k].opt);
}

void bfs() {

	int front = 0, rear = 0, i;
	
	tmp.opt = 0;
	tmp.par = -1;
	if (!strcmp(tmp.str, aim)) return;
	hash(tmp.str);
	queue[rear++] = tmp;

	while (front != rear) {

		tmp = queue[front];
		
		for (i = 0; i < 3; ++i) {

			nxt = tmp;
			(*fun[i])(nxt.str);
			if (hash(nxt.str)) continue;

			nxt.opt = opt[i];
			nxt.par = front;
			queue[rear] = nxt;
			if (!strcmp(nxt.str, aim)) {

				print(rear);
				return;
			}
			++rear;
		}
		++front;
	}
}

int main() {

	fun[0] = optA;
	fun[1] = optB;
	fun[2] = optC;

	while (scanf("%s", tmp.str) != EOF) {

		scanf("%s", aim);
		swap(&tmp.str[4], &tmp.str[7]);
		swap(&tmp.str[5], &tmp.str[6]);
		swap(&aim[4], &aim[7]);
		swap(&aim[5], &aim[6]);
		memset(vis, 0, sizeof(vis));
		bfs();
		printf("\n");
	}
	return 0;
}