【魔板】 （C++代码）

解题思路:



参考代码:

#include<bits/stdc++.h>
using namespace std;

int AimValue;
bool Vis[49451 + 1];
typedef struct {
	char now[9], OPT[23];
} status;

void Conv(char start[]) {
	swap(start[7], start[4]);
	swap(start[6], start[5]);
}

int Hash(char now[]) {
	int hash; sscanf(now, "%d", &hash);
	return hash % 49451;
}

void optA(char now[], char OPT[]) {
	for (int pos = 0; pos < 4; pos++)
		swap(now[pos], now[pos + 4]);
	strcat(OPT, "A");
}

void optB(char now[], char OPT[]) {
	char tmp; int pos;
	for (pos = 3, tmp = now[3]; pos > 0; pos--)
		now[pos] = now[pos - 1];	now[0] = tmp;
	for (pos = 7, tmp = now[7]; pos > 4; pos--)
		now[pos] = now[pos - 1];	now[4] = tmp;
	strcat(OPT, "B");
}

void optC(char now[], char OPT[]) {
	char tmp = now[1]; now[1] = now[5];
	now[5] = now[6]; now[6] = now[2]; now[2] = tmp;
	strcat(OPT, "C");
}

void BFS(status start) {
	queue<status> que; que.push(start);
	while (!que.empty()) {
		for (int Opts = 1; Opts <= 3; Opts++) {
			status tmp = que.front();
			if (Opts == 1) 
				optA(tmp.now, tmp.OPT);
			else if (Opts == 2) 
				optB(tmp.now, tmp.OPT);
			else
				optC(tmp.now, tmp.OPT);

			int hash = Hash(tmp.now);
			if (hash == AimValue) {
				puts(tmp.OPT); return;
			}
			if (!Vis[hash]) {
				Vis[hash] = true; que.push(tmp);
			}
		}
		que.pop();
	}
}

int main() {
	status start; char aim[9];
	while (cin >> start.now >> aim) {
		memset(start.OPT, 0, sizeof(start.OPT)); memset(Vis, 0, sizeof(Vis));
		Conv(start.now); Conv(aim);
		Vis[Hash(start.now)] = true; AimValue = Hash(aim);
		BFS(start);
	}
}