首页 > 代码库 > [dfs] zoj 3736 Pocket Cube
[dfs] zoj 3736 Pocket Cube
题目链接:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3736
Pocket Cube is a 3-D combination puzzle. It is a 2 × 2 × 2 cube, which means it is constructed by 8 mini-cubes. For a combination of 2 × 2 mini-cubes which sharing a whole cube face, you can twist it 90 degrees in clockwise or counterclockwise direction, this twist operation is called one twist step.
Considering all faces of mini-cubes, there will be totally 24 faces painted in 6 different colors (Indexed from 0), and there will be exactly 4 faces painted in each kind of color. If 4 mini-cubes‘ faces of same color rely on same large cube face, we can call the large cube face as a completed face.
Now giving you an color arrangement of all 24 faces from a scrambled Pocket Cube, please tell us the maximum possible number of completed faces in no more than N twist steps.
Index of each face is shown as below:
Input
There will be several test cases. In each test case, there will be 2 lines. One integer N (1 ≤ N ≤ 7) in the first line, then 24 integers Ci seperated by a sinle space in the second line. For index 0 ≤ i < 24, Ci is color of the corresponding face. We guarantee that the color arrangement is a valid state which can be achieved by doing a finite number of twist steps from an initial cube whose all 6 large cube faces are completed faces.
Output
For each test case, please output the maximum number of completed faces during no more than N twist step(s).
Sample Input
1 0 0 0 0 1 1 2 2 3 3 1 1 2 2 3 3 4 4 4 4 5 5 5 5 1 0 4 0 4 1 1 2 5 3 3 1 1 2 5 3 3 4 0 4 0 5 2 5 2
Sample Output
6 2
Author: FAN, Yuzhe;CHEN, Cong;GUAN, Yao
Contest: The 2013 ACM-ICPC Asia Changsha Regional Contest
题目意思:
给2*2*2的魔方,求在给定的n步内最多可以凑成多少完整的面。
解题思路:
由于n<=7,所以暴搜即可。
每种状态下有6种选择,(不是12种,因为转动右边可以转化为转动左边,转动下面可以转化为转动上面,转动后面可以转化为转动前面)
所以只用考虑左边、下面、后面的各两种情况。
找出各位置新的状态下在原来的位置标号。
Tips: 当数组指针作为参数传给函数时,不能在里面用memcpy,因为此时并不知道该数组的大小
当全局数组指针作为参数传给函数时,每个递归函数里面对指针所指内容所做的修改,都会生效,并且有可能访问的都是同一个内存区域。
当传数组指针时,最好使用局部数组这样才不会有问题。
代码:
//#include<CSpreadSheet.h> #include<iostream> #include<cmath> #include<cstdio> #include<sstream> #include<cstdlib> #include<string> #include<string.h> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #include<bitset> #include<cmath> #define eps 1e-6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define ll __int64 #define LL long long #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #define M 1000000007 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 30 int cur[Maxn],vv[Maxn],n,ans; int next[][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},//左边往外 {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},//下面往外 {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} //后面忘上 }; int cal(int * cur) //统计完整面的个数 { int res=0; if(cur[0]==cur[1]&&cur[0]==cur[2]&&cur[0]==cur[3]) res++; if(cur[4]==cur[5]&&cur[4]==cur[10]&&cur[4]==cur[11]) res++; if(cur[6]==cur[7]&&cur[6]==cur[12]&&cur[6]==cur[13]) res++; if(cur[8]==cur[9]&&cur[8]==cur[14]&&cur[8]==cur[15]) res++; if(cur[16]==cur[17]&&cur[16]==cur[18]&&cur[16]==cur[19]) res++; if(cur[20]==cur[21]&&cur[20]==cur[22]&&cur[20]==cur[23]) res++; return res; } void dfs(int num,int * cur) { ans=max(ans,cal(cur)); if(num>n) return ; int vv[Maxn]; //该数组定义成全局变量会有问题 for(int i=0;i<6;i++) { for(int j=0;j<24;j++) vv[j]=cur[next[i][j]]; //如果vv是全局的,vv和cur会指向同一块内存,访问会出现混乱 dfs(num+1,vv); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while(~scanf("%d",&n)) { for(int i=0;i<24;i++) scanf("%d",&cur[i]); ans=0; dfs(1,cur); printf("%d\n",ans); } return 0; }