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};//err
13 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 }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章