http://acm.hdu.edu.cn/showproblem.php?pid=4801

1. 题目描述

给定一个2×2×22×2×2的魔方，当某个面上的4个小块颜色均相同时，称这个面为complete。求对这个魔方进行n∈[1,7]n∈[1,7]次旋转（沿某个面顺时针或者逆时针）的过程中，求complete的面总和的最大值。魔方及索引如下图所示：

 

我一直以为魔方只有8种操作

上图再加上反方向的就是8种

但其实下面的往右转和上面的往左转是一样的。。。

并且还忽略了红线的操作

那其实我们可以这么考虑，以每个面为平面旋转，有逆时针和顺时针两种

六个面，6*2=12种操作，然后，我们考虑相对的两个面

我们发现

从中间切开的这两个面，比如说上下，其实这两个操作是一种操作

因此12/2=6

一共只有6种操作，这个题目最多转7次，那么一共有6^7=279936这么多状态

挺少的所以我们可以直接DFS爆搜

并且一个显然的剪枝是，如果上一次对某一个面逆时针，那么这次对这个面顺时针就没有必要了，这相当于还原

代码常量较多，不好调试，需要对照立体图和展开图写出对应的排列关系

(旋转某个面时，该面上的排列也会放生变化

1 #include 
      
        2 #include 
       
         3  4 using namespace std; 5 int f[6][4]={
    {
    0,1,2,3},{
    4,5,10,11},{
    6,7,12,13},{
    8,9,14,15},{
    16,17,18,19},{
    20,21,22,23}}; 6 int sour[]={
    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23}; 7 int left0[]={
    2,0,3,1,6,7,8,9,23,22,10,11,12,13,14,15,16,17,18,19,20,21,5,4}; 8 int right0[]={
    1,3,0,2,23,22,4,5,6,7,10,11,12,13,14,15,16,17,18,19,20,21,9,8}; 9 int left1[]={
    20,1,22,3,10,4,0,7,8,9,11,5,2,13,14,15,6,17,12,19,16,21,18,23};10 int right1[]={
    6,1,12,3,5,11,16,7,8,9,4,10,18,13,14,15,20,17,22,19,0,21,2,23};11 int left2[]={
    0,1,8,14,4,3,7,13,17,9,10,2,6,12,16,15,5,11,18,19,20,21,22,23};12 int right2[]={
    0,1,11,5,4,16,12,6,2,9,10,17,13,7,3,15,14,8,18,19,20,21,22,23};//err13 int temp[24],cube[24],ans,n;14 void L0(){15     for(int i=0;i<24;++i) temp[i]=cube[left0[i]];16     for(int i=0;i<24;++i) cube[i]=temp[i];17 }18 void R0(){19     for(int i=0;i<24;++i) temp[i]=cube[right0[i]];20     for(int i=0;i<24;++i) cube[i]=temp[i];21 }22 void L1(){23     for(int i=0;i<24;++i) temp[i]=cube[left1[i]];24     for(int i=0;i<24;++i) cube[i]=temp[i];25 }26 void R1(){27     for(int i=0;i<24;++i) temp[i]=cube[right1[i]];28     for(int i=0;i<24;++i) cube[i]=temp[i];29 }30 void L2(){31     for(int i=0;i<24;++i) temp[i]=cube[left2[i]];32     for(int i=0;i<24;++i) cube[i]=temp[i];33 }34 void R2(){35     for(int i=0;i<24;++i) temp[i]=cube[right2[i]];36     for(int i=0;i<24;++i) cube[i]=temp[i];37 }38 int _cpf(int cube[]){39     int ans=0;40     for(int i=0;i<6;++i){41         if(cube[f[i][0]]==cube[f[i][1]]&&cube[f[i][1]]==cube[f[i][2]]&&cube[f[i][2]]==cube[f[i][3]]) ans++;42     }43     return ans;44 }45 void dfs(int step,int k){46     ans=max(ans,_cpf(cube));47     if(step>=n) return ;48     int tmp[24];49     for(int i=0;i<24;++i) tmp[i]=cube[i];50     if(k!=1){51         L0();dfs(step+1,0);ans=max(ans,_cpf(cube));52         for(int i=0;i<24;++i) cube[i]=tmp[i];53     }54     if(k!=0){55         R0();dfs(step+1,1);ans=max(ans,_cpf(cube));56         for(int i=0;i<24;++i) cube[i]=tmp[i];57     }58     if(k!=3){59         L1();dfs(step+1,2);ans=max(ans,_cpf(cube));60         for(int i=0;i<24;++i) cube[i]=tmp[i];61     }62     if(k!=2){63         R1();dfs(step+1,3);ans=max(ans,_cpf(cube));64         for(int i=0;i<24;++i) cube[i]=tmp[i];65     }66     if(k!=5){67         L2();dfs(step+1,4);ans=max(ans,_cpf(cube));68         for(int i=0;i<24;++i) cube[i]=tmp[i];69     }70     if(k!=4){71         R2();dfs(step+1,5);ans=max(ans,_cpf(cube));72         for(int i=0;i<24;++i) cube[i]=tmp[i];73     }74 }75 int main(){76     while(~scanf("%d",&n)){77         for(int i=0;i<24;++i){78             scanf("%d",cube+i);79         }80         ans=0;81         dfs(0,-1);82         printf("%d\n",ans);83     }84     return 0;85 }