LA 3401 Colored Cubes (搜索 + 暴力)

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4098

首先打表，正方体旋转的 \(24\) 种姿态

枚举所有正方体的旋转状态(第 \(1\) 个正方体不用旋转)，对每个面，保留最多的颜色，其它颜色重涂

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

const int maxn = 4;

int dice24[25][6] = {
{2, 1, 5, 0, 4, 3}, {2, 0, 1, 4, 5, 3}, {2, 4, 0, 5, 1, 3}, {2, 5, 4, 1, 0, 3},
{4, 2, 5, 0, 3, 1}, {5, 2, 1, 4, 3, 0}, {1, 2, 0, 5, 3, 4}, {0, 2, 4, 1, 3, 5},
{0, 1, 2, 3, 4, 5}, {4, 0, 2, 3, 5, 1}, {5, 4, 2, 3, 1, 0}, {1, 5, 2, 3, 0, 4},
{5, 1, 3, 2, 4, 0}, {1, 0, 3, 2, 5, 4}, {0, 4, 3, 2, 1, 5}, {4, 5, 3, 2, 0, 1},
{1, 3, 5, 0, 2, 4}, {0, 3, 1, 4, 2, 5}, {4, 3, 0, 5, 2, 1}, {5, 3, 4, 1, 2, 0},
{3, 4, 5, 0, 1, 2}, {3, 5, 1, 4, 0, 2}, {3, 1, 0, 5, 4, 2}, {3, 0, 4, 1, 5, 2}
};

int n, ans;

vector<string> names;
int dice[maxn][6];
int ID(const char *name){
	string s(name);
	int l = names.size();
	for(int i = 0 ; i < l ; ++i){
		if(names[i] == s) return i;
	} 
	names.push_back(s);
	return l;
}

int r[maxn], color[maxn][6];

void check(){
	for(int i = 0 ; i < n ; ++i)
		for(int j = 0 ; j < 6 ; ++j)
			color[i][dice24[r[i]][j]] = dice[i][j];
		
	int res = 0;	
	for(int j = 0 ; j < 6 ; ++j){
		int mx = 0;
		
		int cnt[maxn * 6];
		memset(cnt, 0, sizeof(cnt));
		for(int i = 0 ; i < n ; ++i){
			mx = max(mx, ++cnt[color[i][j]]);
		}
		res += n - mx;
	}
	ans = min(ans, res);
}

void dfs(int d){
	if(d == n){
		check();
		return;
	}
	
	for(int i = 0 ; i < 24 ; ++i){
		r[d] = i;
		dfs(d + 1);
	}
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘){ s = s * 10 + ch - ‘0‘; ch = getchar(); } return s * f; }

int main(){
	while(scanf("%d", &n) == 1 && n){
		names.clear();
		for(int i = 0 ; i < n ; ++i){
			for(int j = 0 ; j < 6 ; ++j){
				char s[30];
				scanf("%s", s);
				dice[i][j] = ID(s);
			}
		}
		
		ans = n * 6;
		
		r[0] = 0;
		dfs(1);
		
		printf("%d\n", ans);
	}
	return 0;
}

LA 3401 Colored Cubes (搜索 + 暴力)

原文：https://www.cnblogs.com/tuchen/p/14838862.html