LA 3401

彩色立方体、

【分析】

弄清楚24种状态，可以由标准姿态旋转而来。

计算24种状态：

#include <iostream>

#include <string>

int left[] = { ,,,,, };

int up[] = { ,,,,, };

//按照排列T旋转姿态p

void rot(int *T, int *p)

{

    int q[];

    memcpy(q, p, sizeof(q));

    for (int i = ; i < ; i++)

        p[i] = T[q[i]];

}

void enumerate_permutations()

{

    int p0[] = { ,,,,, };

    printf("int dice24[24][6] = {\n");

    for (int i = ; i < ; i++)

    {

        int p[];

        memcpy(p, p0, sizeof(p0));

        if (i == )rot(up, p);

        if (i == ) { rot(left, p); rot(up, p); }

        if (i == ) { rot(up, p); rot(up, p); }

        if (i == ) { rot(left, p); rot(left, p); rot(left, p); rot(up, p); }

        if (i == ) { rot(left, p); rot(left, p); rot(up, p); }

        for (int j = ; j < ; j++)

        {

            printf("{%d,%d,%d,%d,%d,%d},\n", p[], p[], p[], p[], p[], p[]);

            rot(left, p);

        }

    }

    printf("};\n");

}

int main()

{

    enumerate_permutations();

    return ;

}

得到结果

直接用到最终程序中

//2019.4.23 彩色立方体

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

const int maxn = ;

int n, dice[maxn][], ans;

int dice24[][] = {

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

    { ,,,,, },

};

vector<string> names;

int ID(const char* name)

{

    string s(name);

    int n = names.size();

    for (int i = ; i < n; i++)

        if (names[i] == s) return i;

    names.push_back(s);

    return n;

}

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

void check()

{

    for (int i = ; i < n; i++)

        for (int j = ; j < ; j++)

            color[i][dice24[r[i]][j]];

    int tot = ;

    for (int j = ; j < ; j++)

    {

        int cnt[maxn * ];

        memset(cnt, , sizeof(cnt));

        int maxface = ;

        for (int i = ; i < n; i++)

            maxface = max(maxface;
            ++cnt[color[i][j]]);

            tot += n - maxface;

    }

    ans = min(ans, tot);

}

void dfs(int d)

{

    if (d == n) check();

    else for (int i = ; i < ; i++)

    {

        r[d] = i;

        dfs(d + );

    }

}

int main()

{

    while (scanf_s("%d", &n) ==  && n)

    {

        names.clear();

        for(int i=;i<n;i++)

            for (int j = ; j < ; j++)

            {

                char name[];

                scanf_s("%s", name);

                dice[i][j] = ID(name);

            }

        ans = n * ;

        r[] = ;

        dfs();

        printf("%d\n", ans);

    }

    return ;

}