这道题是长沙区域赛的一道简单题，当时题目在ZOJ重现的时候就做了一次，但是做的好复杂，用的BFS暴力，而且还没打表，最后还是莫名其妙的爆栈错误，所以就一直没弄出来，昨天做到大白书上例题05年东京区域赛的一道类似题 Colored Cubes，这类题都需要脑补一下立方体的旋转总共有几种状态，然后用函数或者手工打表来记叙每一次变化之后的立方体变化
这道题从编号开始就给了我们很大便利，从0-23，读入数据也是按照这个来，很方便。我是手工打的表，说实话，魔方的转动还是有点复杂，我还真不知道用函数怎么打出表来。
吐血的是我一开始脑子居然觉得只有4种旋转方式，其实有6种,当然不考虑对应面的旋转，否则就有12种了，很好理解，魔方的一个面顺时针或者逆时针旋转，就相当于对应面的反向运动，因此6个面只需考虑三个面，由此打好表，然后用DFS进行下搜索即可。。。不得不说一下一旦用到DFS剪枝的重要性，由于魔方旋转过程中，可能出现转过去又转回来的情况，但其实是做了无用功，因此可以简单的判断一下是否又转了回来，这样子时间复杂度一下从1000+降到了300+。
#include <iostream> #include <cstdio> #include <cstring> int clocks[6][24]={ {6,1,12,3,5,11,16,7,8,9,4,10,18, 13,14,15,20,17,22,19,0,21,2,23}, {20,1,22,3,10,4,0,7,8,9,11,5,2, 13,14,15,6,17,12,19,16,21,18,23}, {2,0,3,1,6,7,8,9,23,22,10,11,12, 13,14,15,16,17,18,19,20,21,5,4}, {1,3,0,2,23,22,4,5,6,7,10,11,12, 13,14,15,16,17,18,19,20,21,9,8}, {0,1,11,5,4,16,12,6,2,9,10,17,13, 7,3,15,14,8,18,19,20,21,22,23}, {0,1,8,14,4,3,7,13,17,9,10,2,6,12, 16,15,5,11,18,19,20,21,22,23}, }; int cuba[30],n,ans; int r[10]; inline int max(int a,int b) { if (a>b) return a; else return b; } int judge(int* t) { int flag,tot; tot=6; flag=t[0]; if (flag!=t[1]||flag!=t[2]||flag!=t[3]) tot--; flag=t[4]; if (flag!=t[5]||flag!=t[10]||flag!=t[11]) tot--; flag=t[6]; if (flag!=t[7]||flag!=t[12]||flag!=t[13]) tot--; flag=t[8]; if (flag!=t[9]||flag!=t[14]||flag!=t[15]) tot--; flag=t[16]; if (flag!=t[17]||flag!=t[18]||flag!=t[19]) tot--; flag=t[20]; if (flag!=t[21]||flag!=t[22]||flag!=t[23]) tot--; return tot; } void solve(int x) { int temp[30],i,j; memcpy(temp,cuba,sizeof (cuba)); for (i=0;i<x;i++) { int tt[30]; memcpy(tt,temp,sizeof (temp)); for (j=0;j<24;j++) { temp[j]=tt[clocks[r[i]][j]]; } } ans=max(ans,judge(temp)); } void dfs(int x) { if (ans==6) return; solve(x); if (x==n) return; else { for (int i=0;i<6;i++) { if (x>2 && i==r[x-1] && i==r[x-2] && i==r[x-3]) //这个和下面那句都是剪枝条件，尤其是下面那句剪枝效果明显，避免重复的搜索。 continue; if (x>0 && (i^1)==r[x-1]) continue; r[x]=i; dfs(x+1); } } } int main() { while (scanf("%d",&n)!=EOF) { for (int i=0;i<24;i++) scanf("%d",&cuba[i]); ans=0; memset(r,0,sizeof r); dfs(0); printf("%d ",ans); } return 0; }