题解 P1780 【染色的立方体_NOI导刊2010提高（03）】

「QQ红包」 · 2017-07-04 15:05:12 · 题解

刘汝佳的训练指南上的一道题，基本上是暴搜

24种方式打表

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int qp[24][6] = 
{
{2, 1, 5, 0, 4, 3},
{2, 0, 1, 4, 5, 3},
{2, 4, 0, 5, 1, 3},
{2, 5, 4, 1, 0, 3},
{4, 2, 5, 0, 3, 1},
{5, 2, 1, 4, 3, 0},
{1, 2, 0, 5, 3, 4},
{0, 2, 4, 1, 3, 5},
{0, 1, 2, 3, 4, 5},
{4, 0, 2, 3, 5, 1},
{5, 4, 2, 3, 1, 0},
{1, 5, 2, 3, 0, 4},
{5, 1, 3, 2, 4, 0},
{1, 0, 3, 2, 5, 4},
{0, 4, 3, 2, 1, 5},
{4, 5, 3, 2, 0, 1},
{1, 3, 5, 0, 2, 4},
{0, 3, 1, 4, 2, 5},
{4, 3, 0, 5, 2, 1},
{5, 3, 4, 1, 2, 0},
{3, 4, 5, 0, 1, 2},
{3, 5, 1, 4, 0, 2},
{3, 1, 0, 5, 4, 2},
{3, 0, 4, 1, 5, 2},
};
map<string,int> name;
int d;//颜色编号 
int n,i,j;
char ch[26];
int ans;
int a[5][7];//存原本颜色 
int r[5];//存每个立方体用的姿态编号 
int co[5][7];
int sum[25];
int maxx;
void check()
{
    for (int ii=0;ii<n;ii++)
        for (int jj=0;jj<6;jj++)
        {
            co[ii][qp[r[ii]][jj]]=a[ii][jj]; 
        }
    int t=0;
    for (int jj=0;jj<6;jj++)
    {
        memset(sum,0,sizeof(sum));//清空
        maxx=0;
        for (int ii=0;ii<n;ii++)
        {
            sum[co[ii][jj]]++;
            maxx=max(sum[co[ii][jj]],maxx);
        }
        t=t+(n-maxx);
    }
    ans=min(t,ans);
} 
void dfs(int x)
{
    if (x==n) 
    {
        check();//搜完了
        return;
    }
    else 
    for (int ii=0;ii<24;ii++)//继续搜 
    {
        r[x]=ii;
        dfs(x+1);
    } 
    return;
}
int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        name.clear();
        d=0;
        if (n==0) return 0;
        for (i=0;i<n;i++)
            for (j=0;j<6;j++)
            {
                scanf("%s",ch);
                if (name[ch]==0)
                {
                    d++;
                    name[ch]=d;
                    a[i][j]=d;//第i个立方体第j个面 颜色 标号 
                } else a[i][j]=name[ch];
            }
        ans=n*6;//最大所有的都涂嘛
        r[0]=0;//0不旋转
        dfs(1); 
        printf("%d\n",ans);
    }
    return 0;
}