学步园

本题旋转方法很特别，先确定右旋和上旋，则每个面朝上都可以通过这两种操作实现；

再者，是暴力的角度，要从最优解出发，肯定可以确定的是每个立方体都为24种旋转方案中的一种；

则不如取第一个 只采用 24种旋转方式中的一种，然后枚举其他立方体的旋转方式，然后既然状态确定的情况下，就好统计了，每个面取n个立方体出现最多的内个颜色；

最坏复杂度 4 * 24^4; 一百万左右；

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 4;

int Right[] = {4,0,2,3,5,1};
int up[] = {3,1,0,5,4,2};
void rotate(int* A,int* B){
  int C[6];
  memcpy(C,B,sizeof(C));
  for(int i=0;i<6;i++){
    B[i] = C[A[i]];
  }
}
int dice[24][6];
void init(){
  int p0[] = {0,1,2,3,4,5};
  for(int i=0;i<=6;i++){
    int temp[6];
    memcpy(temp,p0,sizeof(temp));
    if(i==0) rotate(up,temp);
    if(i==1) {rotate(Right,temp); rotate(up,temp);  rotate(up,temp); rotate(up,temp);}
    if(i==3) {rotate(up,temp); rotate(up,temp);}
    if(i==4) {rotate(Right,temp); rotate(up,temp);}
    if(i==5) {rotate(up,temp);  rotate(up,temp); rotate(up,temp);}
    for(int j=0;j<4;j++){
      rotate(Right,temp);
      for(int k=0;k<6;k++)
        dice[i*4+j][k] = temp[k];
    }
  }
}
int ans,r[maxn],yuan[maxn][6],color[maxn][6],n;
void check(){
  for(int i=0;i<n;i++)
    for(int j=0;j<6;j++){
      color[i][j] = yuan[i][dice[r[i]][j]];
  }
  int tot=0;
  for(int j=0;j<6;j++){
    int maxface = 0;
    int cnt[maxn*6]={0};
    for(int i=0;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(); return ;
  }
  for(int i=0;i<24;i++){
     r[d] = i;
     dfs(d+1);
  }
}
vector<string> names;
int ID(char* str){
  string s(str);
  for(int i=0;i<names.size();i++){
     if(names[i]==s) return i;
  }
  names.push_back(s);
  return names.size()-1;
}
char str[1000];
int main()
{
    init();
    while(scanf("%d",&n)==1 && n){
      names.clear();
      for(int i=0;i<n;i++){
        for(int j=0;j<6;j++){
            scanf("%s",str);
            yuan[i][j] = ID(str);
        }
      }
      r[0] = 0;
      ans = n*6;
      dfs(1);
      printf("%d\n",ans);
    }
    return 0;
}