UVa 1352 - Colored Cubes

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給予最多 4 個骰子,修改最少的面,使得每個骰子同構。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
3 
scarlet green blue yellow magenta cyan
blue pink green magenta cyan lemon
purple red blue yellow cyan green
2
red green blue yellow magenta cyan
cyan green blue yellow magenta red
2
red green gray gray magenta cyan
cyan green gray gray magenta red
2
red green blue yellow magenta cyan
magenta red blue yellow cyan green
3
red green blue yellow magenta cyan
cyan green blue yellow magenta red
magenta red blue yellow cyan green
3
blue green green green green blue
green blue blue green green green
green green green green green sea-green
3
red yellow red yellow red yellow
red red yellow yellow red yellow
red red red red red red
4
violet violet salmon salmon salmon salmon
violet salmon salmon salmon salmon violet
violet violet salmon salmon violet violet
violet violet violet violet salmon salmon
1
red green blue yellow magenta cyan
4
magenta pink red scarlet vermilion wine-red
aquamarine blue cyan indigo sky-blue turquoise-blue
blond cream chrome-yellow lemon olive yellow
chrome-green emerald-green green olive vilidian sky-blue
0

Sample Output

1
2
3
4
5
6
7
8
9
10
4 
2
0
0
2
3
4
4
0
16

Solution

由於每個骰子有 24 種同構排列,複雜度 O(24^4)

將排列對齊後,使用貪心算法,將每一個 column 找到最多相同元素,剩餘的就是最少修改元素。

類似漢明距離的最少修改。順便將之前的代碼重新構造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

struct DICE {
int dice[6]; // front, right, up, back, left, down
void rightTurn() {
static int t;
t = dice[0], dice[0] = dice[4];
dice[4] = dice[3], dice[3] = dice[1], dice[1] = t;
}
void upTurn() {
static int t;
t = dice[0], dice[0] = dice[5];
dice[5] = dice[3], dice[3] = dice[2], dice[2] = t;
}
void clockwise() {
static int t;
t = dice[2], dice[2] = dice[4];
dice[4] = dice[5], dice[5] = dice[1], dice[1] = t;
}
void print() {
for (int i = 0; i < 6; i++)
printf("%d ", dice[i]);
puts("");
}
vector<DICE> generate() {
vector<DICE> ret;
DICE tmp = *this;

for (int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
ret.push_back(tmp);
tmp.clockwise();
}
tmp.rightTurn();
}
tmp.upTurn();
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 4; j++) {
ret.push_back(tmp);
tmp.clockwise();
}
tmp.upTurn(), tmp.upTurn();
}
return ret;
}
bool operator<(const DICE &x) const {
for (int i = 0; i < 6; i++)
if (dice[i] != x.dice[i])
return dice[i] < x.dice[i];
return false;
}
bool operator==(const DICE &x) const {
for (int i = 0; i < 6; i++)
if (dice[i] != x.dice[i])
return false;
return true;
}
};

int path[8];
vector<DICE> kind[8];
vector<DICE> permutation;
int ret = 0x3f3f3f3f, N;
int counter[32];
void dfs(int idx) {
if (idx == N) {
int ch = 0;
for (int i = 0; i < 6; i++) {
int mx = 0;
memset(counter, 0, sizeof(counter));
for (int j = 0; j < N; j++)
mx = max(mx, ++counter[kind[j][path[j]].dice[i]]);
ch += N - mx;
if (ch >= ret) return ;
}
ret = min(ret, ch);
return ;
}
for (int i = 0; i < kind[idx].size(); i++) {
path[idx] = i;
dfs(idx+1);
}
}
int main() {
DICE p;
for (int i = 0; i < 6; i++)
p.dice[i] = i;
permutation = p.generate();

char s[128];
while (scanf("%d", &N) == 1 && N) {
map<string, int> colors;
for (int i = 0; i < N; i++) {
int v[6];
for (int j = 0; j < 6; j++) {
scanf("%s", s);
int &x = colors[s];
if (x == 0) x = colors.size();
v[j] = x;
}
DICE D;
D.dice[0] = v[0], D.dice[1] = v[1], D.dice[2] = v[2];
D.dice[5] = v[3], D.dice[4] = v[4], D.dice[3] = v[5];

kind[i] = D.generate();
sort(kind[i].begin(), kind[i].end());
kind[i].resize(unique(kind[i].begin(), kind[i].end()) - kind[i].begin());
// printf("%d\n", kind[i].size());
}

ret = 0x3f3f3f3f;
dfs(0);
printf("%d\n", ret);
}
return 0;
}