2344.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2344 on 2006-09-09 at 10:36:51 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
 
const int FACE[][6] = { { 3, 1, 2, 6, 5, 4 }, { 3, 2, 6, 5, 1, 4 }, { 3, 6, 5, 1, 2, 4 }, 
						{ 3, 5, 1, 2, 6, 4 }, { 4, 1, 5, 6, 2, 3 }, { 4, 5, 6, 2, 1, 3 }, 
						{ 4, 6, 2, 1, 5, 3 }, { 4, 2, 1, 5, 6, 3 }, { 1, 2, 3, 5, 4, 6 },
						{ 1, 3, 5, 4, 2, 6 }, { 1, 5, 4, 2, 3, 6 }, { 1, 4, 2, 3, 5, 6 },
						{ 6, 2, 4, 5, 3, 1 }, { 6, 4, 5, 3, 2, 1 }, { 6, 5, 3, 2, 4, 1 }, 
						{ 6, 3, 2, 4, 5, 1 }, { 2, 1, 4, 6, 3, 5 }, { 2, 4, 6, 3, 1, 5 },
						{ 2, 6, 3, 1, 4, 5 }, { 2, 3, 1, 4, 6, 5 }, { 5, 1, 3, 6, 4, 2 },
						{ 5, 3, 6, 4, 1, 2 }, { 5, 6, 4, 1, 3, 2 }, { 5, 4, 1, 3, 6, 2 } };
 
struct cmp {
	bool operator ()(const char* s1, const char* s2) const
		{ return strcmp(s1, s2) < 0; }
};
 
char name[1024][36];
int cn, best, pos[4], n;
map<char*, int, cmp> dict;
 
int order(char*);
 
class Cube {
public:
	int f[6], pos;
	void make();
	int face(int k) const { return f[k-1]; }
};
void Cube::make() {
	for(int i = 0; i < 6; i++) {
		char nm[36]; scanf("%s", nm);
		f[i] = order(nm);
	}
}
 
Cube cube[4];
void find(int);
 
int main()
{
	while(scanf("%d", &n) != EOF && n != 0) {
		dict.clear();
		cn = 0; best = 1 << 20;
		for(int i = 0; i < n; i++) cube[i].make();
		pos[0] = 0; find(1);
		printf("%d\n", best);
	}
	
	return 0;
}
 
int order(char* nm)
{
	if(!dict.count(nm)) {
		strcpy(name[cn], nm);
		dict[name[cn]] = cn;
		cn++;
	}
	return dict.find(nm)->second;
}
void find(int k)
{
	if(k != n) {
		for(int i = 0; i < 24; i++) { pos[k] = i; find(k+1); }
	} else {
		int tb = 0;
		for(int i = 0; i < 6; i++) {
			int sn = 1 << 20;
			for(int j = 0; j < n; j++) {
				int tx = 0;
				for(int x = 0; x < n; x++)
					if(cube[j].face(FACE[pos[j]][i]) == cube[x].face(FACE[pos[x]][i])) tx++;
				sn <?= n-tx;
			}
			tb += sn;
		}
		best <?= tb;
	}
}