题目

图比较多,看原题吧

There are several colored cubes.
All of them are of the same size but they may be colored differently.

Each face of these cubes has a single color.
Colors of distinct faces of a cube may or may not be the same.

Two cubes are said to be identically colored if some suitable rotations of one of the cubes give identical looks to both of the cubes.
For example, two cubes shown in Figure 2 are identically colored.

A set of cubes is said to be identically colored if every pair of them are identically colored.

A cube and its mirror image are not necessarily identically colored.
For example, two cubes shown in Figure 3 are not identically colored.

You can make a given set of cubes identically colored by repainting some of the faces, whatever colors the faces may have.
In Figure 4, repainting four faces makes the three cubes identically colored and repainting fewer faces will never do.

Your task is to write a program to calculate the minimum number of faces that needs to be repainted for a given set of cubes to become identically colored.

Input

The input is a sequence of datasets.
A dataset consists of a header and a body appearing in this order.

A header is a line containing one positive integer n and the body following it consists of n lines.
You can assume that 1 ≤ n ≤ 4.
Each line in a body contains six color names separated by a space.
A color name consists of a word or words connected with a hyphen (-).
A word consists of one or more lowercase letters.
You can assume that a color name is at most 24-characters long including hyphens.

A dataset corresponds to a set of colored cubes.
The integer n corresponds to the number of cubes.

Each line of the body corresponds to a cube and describes the colors of its faces.
Color names in a line
is ordered in accordance with the numbering of faces shown in Figure 5.
A line color1 color2 color3 color4 color5 color 6 corresponds to a cube colored as shown in Figure 6.

The end of the input is indicated by a line containing a single zero.
It is not a dataset nor a part of a dataset.

Figure 2: Identically colored cubes
Figure 3: cubes that are not identically colored
Figure 4: An example of recoloring
Figure 5: Numbering of faces Figure 6: Coloring

Output

For each dataset, output a line containing the minimum number of faces that need to be repainted to
make the set of cub es identically colored.

Sample Input

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

4
2
0
0
2
3
4
4
0
16

题解

第一个难点在于同一个立方体有不同的表示方式
可以从任一个面开始,向它相邻的 4 个面进行描述这个立方体,因此每个立方体有 24 种描述方式

最初的想法是,计算每两个立方体的每种形态之间的 “距离”
计算出最少的组合

最后发现有小问题: 最后的形态可能和之前每一种都不一样

因此需要 将每个面涂成当前面颜色最多的面

因此需要枚举所有情况,在每种描述方式下,计算每个面的最少的涂色方法

循环的层数不定,采用递归的方式
最后用一个函数判断对应每个方块的描述方式的情况下最少的涂色方案

时间复杂度比较高,本地机子跑了 15s
本来觉得肯定 TLE 结果竟然过了……

不过该优化的地方还是要优化的,如果结果出现 0 证明已经找到结果了
应该及时跳出循环

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 5;
const int order[24][6] = {
    {1,2,3,4,5,6},
    {1,3,5,2,4,6},
    {1,4,2,5,3,6},
    {1,5,4,3,2,6},
    {2,1,4,3,6,5},
    {2,3,1,6,4,5},
    {2,4,6,1,3,5},
    {2,6,3,4,1,5},
    {3,1,2,5,6,4},
    {3,2,6,1,5,4},
    {3,5,1,6,2,4},
    {3,6,5,2,1,4},
    {4,1,5,2,6,3},
    {4,2,1,6,5,3},
    {4,5,6,1,2,3},
    {4,6,2,5,1,3},
    {5,1,3,4,6,2},
    {5,3,6,1,4,2},
    {5,4,1,6,3,2},
    {5,6,4,3,1,2},
    {6,2,4,3,5,1},
    {6,3,2,5,4,1},
    {6,4,5,2,3,1},
    {6,5,3,4,2,1}
};

struct Cube {
    string v[6];
};

Cube cube[maxn];
int dis[maxn][maxn];

//计算n个正方体,分别取a b c d视图的最优解
int calc(int n,int a = -1,int b = -1,int c = -1,int d = -1) {
    int num[] = {a,b,c,d};
    map<string,int> m;
    int cnt[maxn];

    int sum = 0;
    for(int k = 0;k < 6;k++) {
        //循环计算6个面
        memset(cnt,0,sizeof(cnt));
        m.clear();
        int pos = 0;
        for(int i = 0;i < n;i++) {
            //第i个方块
            int str = order[num[i]][k] - 1;//第i个方块第k个面在制定次序下的编号
            if(m.count(cube[i].v[str]) == 0)
                m.insert(pair<string,int>(cube[i].v[str],pos++));
            cnt[m[cube[i].v[str]]]++;
        }
        sort(cnt,cnt + pos);
        sum += n - cnt[pos - 1];
    }

    return sum;
}

int dfs(int n,int it,int a = -1,int b = -1,int c = -1,int d = -1) {
    if(it == 0) {
        return calc(n,a,b,c,d);
    } else {
        int num[] = {a,b,c,d};
        int Min = INF;

        for(int i = 0;i < 24;i++) {
            num[n - it] = i;
            Min = min(Min,dfs(n,it - 1,num[0],num[1],num[2],num[3]));
            if(Min == 0)
                return 0;
        }

        return Min;
    }
}

bool Do() {
    int n;
    cin >> n;
    if(n == 0)
        return false;
    for(int i = 0;i < n;i++)
        for(int j = 0;j < 6;j++)
            cin >> cube[i].v[j];

    cout << dfs(n,n - 1,0) << endl;

    return true;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    while(Do());

    return 0;
}