AOJ 1259 Colored Cubes
Colored Cubes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1259
問題概要
色が塗られたキューブが4個まで与えられる。
すべて同じキューブにするには、何回塗り替えればいいか。
解法
全探索。
一つのサイコロを固定して、後を回す。
回した結果、ある面について、最も多い色ですべてのサイコロを塗る。
全部の面について行い、最小値を取る。
ソースの一部
int n, choice[4]; int solve(int now){ if(now == n){ int ret = 0; rep(i, 6){ map<int, int> M; int maxi = 0; rep(j, n){ M[data[j][choice[j]].m[i]]++; maxi = max(maxi, M[data[j][choice[j]].m[i]]); } ret += n - maxi; } return ret; } int ret = INF; if(now == 0){ choice[now] = 0; ret = min(solve(now+1), ret); return ret; } rep(i, 24){ choice[now] = i; ret = min(solve(now+1), ret); } return ret; } int main(){ while(cin >> n){ if(n == 0)break; map<string, int> C; int cnt = 1; rep(i, n){ int col[6]; rep(j, 6){ string tmp; cin >> tmp; if(C[tmp] == 0){ C[tmp] = cnt++; } col[j] = C[tmp]; } generate_all(i, (Dice){col}); } cout << solve(0) << endl; } return 0; }