解題區/解題區 - UVa

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;
}