1892.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1892 on 2006-02-15 at 02:24:56 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 1 << 24;
const int LINE[] = { 0, 1, 0, 1, 2, 2, -1, 2, -1, 2, 2, 0, 1, 3, 3, -1, 3, -1, 3, 3, 0, 1, 0, 1 };
const int POS[] =  { 0, 0, 1, 1, 0, 1, -1, 2, -1, 3, 4, 2, 2, 0, 1, -1, 2, -1, 3, 4, 3, 3, 4, 4 };
const int LINE_O[] = { 0, 1, 2, 3, 1, 0, 3, 2 };
const int CROSS[][2] = { { 0, 2 }, { 1, 3 }, { 0, 1 }, { 2, 3 } };
const int OPPO[] = { 5, 4, 7, 6, 1, 0, 3, 2 };
const bool LEFT[] = { false, false, true, true, true, true, false, false };
const int END = 2164815;

int rotate(int, int);
void travel();

char step[MAX];

int main()
{
	int i, j, k, block[32], init[3];
	
	memset(step, -1, sizeof(step)); travel();
	while(scanf("%d", &block[0]) != EOF && block[0] != 0) {
		for(i = 1; i < 24; i++) scanf("%d", &block[i]);
		memset(init, 0, sizeof(init)); int tn;
		for(tn = i = 0; i < 24; i++) {
			int &x = init[block[i]-1];
			if(LINE[i] == -1) x |= 1 << (tn++);
			else x |= 1 << (LINE[i]*5+POS[i]+4);
		}
		int cost = MAX, on, state;
		for(i = 0; i < 3; i++) {
			bool update = false; int spn = step[init[i]]>>3;
			if(cost > spn)  update = true;
			else if(cost == spn) {
				for(j = state, k = init[i]; step[j] == step[k]; j = rotate(j, step[j]&7), k =  rotate(k, step[k]&7));
				if(step[j] > step[k]) update = true;
			}
			if(update) cost = spn, on = i+1, state = init[i];
		}
		if(cost == 0) printf("No moves needed");
		else for(i = state; i != END; i = rotate(i, step[i]&7)) putchar((step[i]&7)+'A');
		printf("\n%d\n", on);
	}
	
	return 0;
}

int rotate(int state, int o)
{
	int i, line[4], sq = state&15, lo = LINE_O[o];
	for(state >>= 4, i = 0; i < 4; i++, state >>= 5) line[i] = state&31;
	int all = ((line[lo]&24)<<2) | (((sq>>CROSS[lo][1])&1)<<4) | 
				((line[lo]&4)<<1) | (((sq>>CROSS[lo][0])&1)<<2) | (line[lo]&3);
	if(LEFT[o]) all = ((all<<1) | (all>>6)) & 127;
	else all = (all>>1) | ((all&1)<<6);
	line[lo] = ((all>>5)<<3) | (((all>>3)&1)<<2) | (all&3);
	for(i = 0; i < 4; i++) {
		int m = (sq>>i)&1;
		if(i == CROSS[lo][0]) m = (all>>2)&1;
		else if(i == CROSS[lo][1]) m = (all>>4)&1;
		state |= (line[i]<<(5*i+4)) | (m<<i);
	}
	return state;
}
void travel()
{
	queue<int> Q;
	step[END] = 0; Q.push(END);
	while(!Q.empty()) {
		int i, st = Q.front(), n = step[st]>>3; Q.pop();
		for(i = 0; i < 8; i++) {
			int nst = rotate(st, OPPO[i]);
			if(step[nst] == -1 || ((step[nst]>>3) == n+1 && (step[nst]&7) > i)) {
				if(step[nst] == -1) Q.push(nst);
				step[nst] = ((n+1)<<3) | i;
			}
		}
	}
}