uva1352 Colored Cubes LA3401

白书第一章例题8

好麻烦！

正方体每面编号为0-5，那么根据顶点和正面，就能确定形态。一共6*4=24种形态。

P[i]表示编号i所在位置。比如P[1]=3，表示第二面转到了第四面。

就可以表示出所有形态。

这时候可以手算或者写个函数找出所有形态。

注意选择函数计算，要放到main外面，方便调。

注意到每个形态都可以由基本姿态左旋上旋得到，而左上旋很接近，就可以模块化了。

然后枚举染色情况。取一个正方体不转（作为参考系，套路了），然后枚举其他三个的情况，然后分别计算6个面。

#include <iostream>

#include <cstring>

#include <vector>

#include <string>

using namespace std;

const int maxn = ;

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

vector<string> names;

int dice24[][];

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

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

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

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()

{

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

    int times = ;

    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++)

        {

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

            {

                dice24[times][k] = p[k];

            }

            rot(Left,p);

            times++;

        }

    }

}

int get_ID(string name)

{

    int n = names.size();

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

    {

        if (names[i] == name)

            return i;

    }

    names.push_back(name);

    return n;

}

void check()

{

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

    {

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

        {

            color[i][dice24[r[i]][j]] = dice[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()

{

    enumerate();

    while (cin>>N && N)

    {

        names.clear();

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

        {

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

            {

                string name;

                cin>>name;

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

            }

        }

        ans = N*;

        r[] = ;

        dfs();

        cout<<ans<<endl;

    }

    return ;

}

巴特西

uva1352 Colored Cubes LA3401

最新文章

热门文章