HDU-6202 cube cube cube
宣原
就是一道暴力模拟魔方旋转的题目，因为限制只有三步，所以纯暴力dfs就可以
先找出魔方的旋转数组，然后写函数按照旋转数组模拟旋转
刚开始我以为只有12种旋转，后来发现有24种，因为懒得再找旋转数组，就写了整个旋转魔方的函数
就是先以1面为顶，转12次，再以7面为顶转8次，再以6为顶转4次
最后结果还行，能15ms过
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int R1[3][5]={9,0,0,0,0,23,0,0,0,0,64,0,0,0,0};
int L1[3][5]={5,0,0,0,0,46,0,0,0,0,27,0,0,0,0};
int U1[3][5]={68,0,0,0,0,19,0,0,0,0,54,0,0,0,0};
int F1[3][5]={14,0,0,0,0,55,0,0,0,0,36,0,0,0,0};
int R2[3][5]={
14,15,16,17,18,
63,62,58,57,55,
37,39,38,42,41
};
int L2[3][5]={
45,44,40,39,37,
55,57,56,60,59,
32,33,34,35,36
};
int U2[3][5]={
36,35,31,30,28,
10,12,11,15,14,
41,42,43,44,45
};
int F2[3][5]={
54,53,49,48,46,
64,66,65,69,68,
5,6,7,8,9
};
int ML1[3][5]={
7,6,2,0,0,
22,26,25,0,0,
47,48,49,0,0
};
int ML2[3][5]={
31,30,29,0,0,
61,62,58,0,0,
38,42,43,0,0
};
int MR1[3][5]={
7,8,4,0,0,
20,24,25,0,0,
67,66,65,0,0
};
int MR2[3][5]={
11,12,13,0,0,
61,60,56,0,0,
40,44,43,0,0
};
int cube[100];
bool judge()
{
for(int i=0;i<8;i++)
{
int t=i*9;
for(int j=1;j<9;j++)
if(cube[j+t]!=cube[j+t+1])
return false;
}
return true;
}
void turn0(int x1[][5],int x2[][5],int t1,int t2,int f)
{
int a[10];
for(int i=0;i<t1;i++)
a[i]=cube[x1[0][i]];
for(int i=0;i<2;i++)
for(int j=0;j<t1;j++)
cube[x1[i][j]]=cube[x1[i+1][j]];
for(int j=0;j<t1;j++)
cube[x1[2][j]]=a[j];
for(int i=0;i<t2;i++)
a[i]=cube[x2[0][i]];
for(int i=0;i<2;i++)
for(int j=0;j<t2;j++)
cube[x2[i][j]]=cube[x2[i+1][j]];
for(int j=0;j<t2;j++)
cube[x2[2][j]]=a[j];
if(f==-1) return;
int t=(f-1)*9;
int k=cube[t+1];
cube[t+1]=cube[t+5];cube[t+5]=cube[t+9];cube[t+9]=k;
k=cube[t+3];cube[t+3]=cube[t+6];cube[t+6]=cube[t+8];cube[t+8]=k;
k=cube[t+2];cube[t+2]=cube[t+7];cube[t+7]=cube[t+4];cube[t+4]=k;
k=cube[t+1];cube[t+1]=cube[t+5];cube[t+5]=cube[t+9];cube[t+9]=k;
k=cube[t+3];cube[t+3]=cube[t+6];cube[t+6]=cube[t+8];cube[t+8]=k;
k=cube[t+2];cube[t+2]=cube[t+7];cube[t+7]=cube[t+4];cube[t+4]=k;
}
void turn1(int x1[][5],int x2[][5],int t1,int t2,int f)
{
int a[10];
for(int i=0;i<t1;i++)
a[i]=cube[x1[2][i]];
for(int i=2;i>0;i--)
for(int j=0;j<t1;j++)
cube[x1[i][j]]=cube[x1[i-1][j]];
for(int j=0;j<t1;j++)
cube[x1[0][j]]=a[j];
for(int i=0;i<t2;i++)
a[i]=cube[x2[2][i]];
for(int i=2;i>0;i--)
for(int j=0;j<t2;j++)
cube[x2[i][j]]=cube[x2[i-1][j]];
for(int j=0;j<t2;j++)
cube[x2[0][j]]=a[j];
if(f==-1) return;int t=(f-1)*9;
int k=cube[t+1];
cube[t+1]=cube[t+5];cube[t+5]=cube[t+9];cube[t+9]=k;
k=cube[t+3];cube[t+3]=cube[t+6];cube[t+6]=cube[t+8];cube[t+8]=k;
k=cube[t+2];cube[t+2]=cube[t+7];cube[t+7]=cube[t+4];cube[t+4]=k;
}
void r1()
{
int a[10];
for(int i=1;i<=9;i++) a[i]=cube[i];
for(int i=1;i<=9;i++) cube[i]=cube[54+i];
for(int i=1;i<=9;i++) cube[54+i]=a[i];
for(int i=1;i<=9;i++) a[i]=cube[18+i];
for(int i=1;i<=9;i++) cube[18+i]=cube[36+i];
for(int i=1;i<=9;i++) cube[36+i]=a[i];
for(int i=1;i<=9;i++) a[i]=cube[9+i];
for(int i=1;i<=9;i++) cube[9+i]=cube[45+i];
for(int i=1;i<=9;i++) cube[45+i]=a[i];
for(int i=1;i<=9;i++) a[i]=cube[27+i];
for(int i=1;i<=9;i++) cube[27+i]=cube[63+i];
for(int i=1;i<=9;i++) cube[63+i]=a[i];
}
void r2()
{
r1();
int a[10];
for(int i=1;i<=9;i++) a[i]=cube[63+i];
for(int i=1;i<=9;i++) cube[63+i]=cube[54+i];
for(int i=1;i<=9;i++) cube[54+i]=cube[45+i];
for(int i=1;i<=9;i++) cube[45+i]=cube[36+i];
for(int i=1;i<=9;i++) cube[36+i]=a[i];
for(int i=1;i<=9;i++) a[i]=cube[27+i];
for(int i=1;i<=9;i++) cube[27+i]=cube[18+i];
for(int i=1;i<=9;i++) cube[18+i]=cube[9+i];
for(int i=1;i<=9;i++) cube[9+i]=cube[i];
for(int i=1;i<=9;i++) cube[i]=a[i];
}
void r3()
{
int a[10];
for(int i=1;i<=9;i++) a[i]=cube[i];
for(int i=1;i<=9;i++) cube[i]=cube[9+i];
for(int i=1;i<=9;i++) cube[9+i]=cube[18+i];
for(int i=1;i<=9;i++) cube[18+i]=cube[27+i];
for(int i=1;i<=9;i++) cube[27+i]=a[i];
for(int i=1;i<=9;i++) a[i]=cube[36+i];
for(int i=1;i<=9;i++) cube[36+i]=cube[45+i];
for(int i=1;i<=9;i++) cube[45+i]=cube[54+i];
for(int i=1;i<=9;i++) cube[54+i]=cube[63+i];
for(int i=1;i<=9;i++) cube[63+i]=a[i];
r1();
}
bool dfs(int d)
{
if(judge()) return true;
if(d==0) return false;
turn0(R1,R2,1,5,6);
if(dfs(d-1)) return true;
turn1(R1,R2,1,5,6);
turn1(R1,R2,1,5,6);
if(dfs(d-1)) return true;
turn0(R1,R2,1,5,6);
turn0(L1,L2,1,5,8);
if(dfs(d-1)) return true;
turn1(L1,L2,1,5,8);
turn1(L1,L2,1,5,8);
if(dfs(d-1)) return true;
turn0(L1,L2,1,5,8);
turn0(U1,U2,1,5,1);
if(dfs(d-1)) return true;
turn1(U1,U2,1,5,1);
turn1(U1,U2,1,5,1);
if(dfs(d-1)) return true;
turn0(U1,U2,1,5,1);
turn0(F1,F2,1,5,5);
if(dfs(d-1)) return true;
turn1(F1,F2,1,5,5);
turn1(F1,F2,1,5,5);
if(dfs(d-1)) return true;
turn0(F1,F2,1,5,5);
turn0(MR1,MR2,3,3,-1);
if(dfs(d-1)) return true;
turn1(MR1,MR2,3,3,-1);
turn1(MR1,MR2,3,3,-1);
if(dfs(d-1)) return true;
turn0(MR1,MR2,3,3,-1);
turn0(ML1,ML2,3,3,-1);
if(dfs(d-1)) return true;
turn1(ML1,ML2,3,3,-1);
turn1(ML1,ML2,3,3,-1);
if(dfs(d-1)) return true;
turn0(ML1,ML2,3,3,-1);
r1();turn0(R1,R2,1,5,6);r1();
if(dfs(d-1)) return true;
r1();turn1(R1,R2,1,5,6);r1();
r1();turn1(R1,R2,1,5,6);r1();
if(dfs(d-1)) return true;
r1();turn0(R1,R2,1,5,6);r1();
r1();turn0(L1,L2,1,5,8);r1();
if(dfs(d-1)) return true;
r1();turn1(L1,L2,1,5,8);r1();
r1();turn1(L1,L2,1,5,8);r1();
if(dfs(d-1)) return true;
r1();turn0(L1,L2,1,5,8);r1();
r1();turn0(U1,U2,1,5,1);r1();
if(dfs(d-1)) return true;
r1();turn1(U1,U2,1,5,1);r1();
r1();turn1(U1,U2,1,5,1);r1();
if(dfs(d-1)) return true;
r1();turn0(U1,U2,1,5,1);r1();
r1();turn0(F1,F2,1,5,5);r1();
if(dfs(d-1)) return true;
r1();turn1(F1,F2,1,5,5);r1();
r1();turn1(F1,F2,1,5,5);r1();
if(dfs(d-1)) return true;
r1();turn0(F1,F2,1,5,5);r1();
r2();turn0(MR1,MR2,3,3,-1);r3();
if(dfs(d-1)) return true;
r2();turn1(MR1,MR2,3,3,-1);r3();
r2();turn1(MR1,MR2,3,3,-1);r3();
if(dfs(d-1)) return true;
r2();turn0(MR1,MR2,3,3,-1);r3();
r2();turn0(ML1,ML2,3,3,-1);r3();
if(dfs(d-1)) return true;
r2();turn1(ML1,ML2,3,3,-1);r3();
r2();turn1(ML1,ML2,3,3,-1);r3();
if(dfs(d-1)) return true;
r2();turn0(ML1,ML2,3,3,-1);r3();
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
for(int i=1;i<=72;i++)
scanf("%d",&cube[i]);
if(dfs(3)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
类似资料：