Skip to content

Instantly share code, notes, and snippets.

@darcyliu darcyliu/cube.c
Created Oct 8, 2014

Embed
What would you like to do?
魔方
// 魔方是一种常见的玩具。2010年7月,美国加利福尼亚州科学家利用计算机证明任意组合的魔方均可以在20步之内还原。作为一个入门级的程序员
// ,我们决定先写一个验证魔方是否复原的程序。对于魔方的一个操作,我们用一个字母来表示。将魔方的一个面正对玩家,就有了前后上下左右六个面,
// 分别用F(Front),B(Back),U(Up),D(Down):,L(Left),R(Right)来表示将这个面顺时针旋转90度,
// 具体玩魔方的时候将右手覆盖到对应的面上,这六个操作时右手的旋转方向都是相同的。同时用X,Y, Z,表示顺时针旋转中间一层,分别对应U,
// R,F。具体情况可以参照下图。与这九个操作对应的还有f,b,u,d,l,r,x,y,z,表示逆时针旋转。
// http://i.imgur.com/hggwjka.png
// 现在我们给出一个操作序列,问在这么旋转之后,魔方是否和原来的时候完全一样。比如UXd被认为是不一样。
// 输入为一个长度不超过200的字符串,仅包含之上定义的18个字母。 如果能复原,输出Yes,否则输出No。
#include <stdio.h>
int cube[6][9];
void trans(int v){
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[v][i];
}
cube[v][0] = memorized[6];
cube[v][1] = memorized[3];
cube[v][2] = memorized[0];
cube[v][3] = memorized[7];
cube[v][4] = memorized[4];
cube[v][5] = memorized[1];
cube[v][6] = memorized[8];
cube[v][7] = memorized[5];
cube[v][8] = memorized[2];
}
void U(){
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[0][i];
}
// 5 -> 0
cube[0][0] = cube[5][0];
cube[0][1] = cube[5][1];
cube[0][2] = cube[5][2];
// 1 - > 5
cube[5][0] = cube[1][8];
cube[5][1] = cube[1][7];
cube[5][2] = cube[1][6];
// 4 - > 1
cube[1][6] = cube[4][2];
cube[1][7] = cube[4][1];
cube[1][8] = cube[4][0];
// 3 - > 0
cube[4][0] = memorized[0];
cube[4][1] = memorized[1];
cube[4][2] = memorized[2];
// 2
trans(2);
}
void R(){
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[2][i];
}
// 0 -> 2
cube[2][2] = cube[0][2];
cube[2][5] = cube[0][5];
cube[2][8] = cube[0][8];
// 3 - > 0
cube[0][2] = cube[3][2];
cube[0][5] = cube[3][5];
cube[0][8] = cube[3][8];
// 1 - > 3
cube[3][2] = cube[1][2];
cube[3][5] = cube[1][5];
cube[3][8] = cube[1][8];
// 3 - > 0
cube[1][2] = memorized[2];
cube[1][5] = memorized[5];
cube[1][8] = memorized[8];
// 5
trans(5);
}
void F(){
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[5][i];
}
// 2 - > 5
cube[5][0] = cube[2][6];
cube[5][3] = cube[2][7];
cube[5][6] = cube[2][8];
// 4 - > 2
cube[2][6] = cube[4][8];
cube[2][7] = cube[4][5];
cube[2][8] = cube[4][2];
// 3 -> 4
cube[4][8] = cube[3][2];
cube[4][5] = cube[3][1];
cube[4][2] = cube[3][0];
// 5 - > 3
cube[3][0] = memorized[6];
cube[3][1] = memorized[3];
cube[3][2] = memorized[0];
// 0
trans(0);
}
void D(){
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[5][i];
}
// 0 - > 5
cube[5][6] = cube[0][6];
cube[5][7] = cube[0][7];
cube[5][8] = cube[0][8];
// 4 - > 0
cube[0][6] = cube[4][6];
cube[0][7] = cube[4][7];
cube[0][8] = cube[4][8];
// 1 -> 4
cube[4][6] = cube[1][2];
cube[4][7] = cube[1][1];
cube[4][8] = cube[1][0];
// 5 - > 1
cube[1][0] = memorized[8];
cube[1][1] = memorized[7];
cube[1][2] = memorized[6];
// 3
trans(3);
}
void L(){
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[0][i];
}
// 2 - > 0
cube[0][0] = cube[2][0];
cube[0][3] = cube[2][3];
cube[0][6] = cube[2][6];
// 1 - > 2
cube[2][0] = cube[1][0];
cube[2][3] = cube[1][3];
cube[2][6] = cube[1][6];
// 3 - > 1
cube[1][0] = cube[3][0];
cube[1][3] = cube[3][3];
cube[1][6] = cube[3][6];
// 0 - > 3
cube[3][0] = memorized[0];
cube[3][3] = memorized[3];
cube[3][6] = memorized[6];
// 4
trans(4);
}
void B() {
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[2][i];
}
// 5 - > 2
cube[2][0] = cube[5][2];
cube[2][1] = cube[5][5];
cube[2][2] = cube[5][8];
// 3 - > 5
cube[5][2] = cube[3][8];
cube[5][5] = cube[3][7];
cube[5][8] = cube[3][6];
// 4 - > 3
cube[3][6] = cube[4][0];
cube[3][7] = cube[4][3];
cube[3][8] = cube[4][6];
// 2 - > 4
cube[4][0] = memorized[2];
cube[4][3] = memorized[1];
cube[4][6] = memorized[0];
// 1
trans(1);
}
void X() {
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[0][i];
}
// 5 - > 0
cube[0][3] = cube[5][3];
cube[0][4] = cube[5][4];
cube[0][5] = cube[5][5];
// 1 - > 5
cube[5][3] = cube[1][5];
cube[5][4] = cube[1][4];
cube[5][5] = cube[1][3];
// 4 - > 1
cube[1][3] = cube[4][5];
cube[1][4] = cube[4][4];
cube[1][5] = cube[4][3];
// 0 - > 4
cube[4][3] = memorized[3];
cube[4][4] = memorized[4];
cube[4][5] = memorized[5];
}
void Y() {
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[2][i];
}
// 0 - > 2
cube[2][1] = cube[0][1];
cube[2][4] = cube[0][4];
cube[2][7] = cube[0][7];
// 3 - > 0
cube[0][1] = cube[3][1];
cube[0][4] = cube[3][4];
cube[0][7] = cube[3][7];
// 1 - > 3
cube[3][1] = cube[1][1];
cube[3][4] = cube[1][4];
cube[3][7] = cube[1][7];
// 2 - > 1
cube[1][1] = memorized[1];
cube[1][4] = memorized[4];
cube[1][7] = memorized[7];
}
void Z(){
int memorized[9];
for (int i = 0; i < 9; ++i)
{
memorized[i] = cube[5][i];
}
// 2 - > 5
cube[5][1] = cube[2][3];
cube[5][4] = cube[2][4];
cube[5][7] = cube[2][5];
// 4 - > 2
cube[2][3] = cube[4][7];
cube[2][4] = cube[4][4];
cube[2][5] = cube[4][1];
// 3 - > 4
cube[4][1] = cube[3][3];
cube[4][4] = cube[3][4];
cube[4][7] = cube[3][5];
// 5 - > 3
cube[3][3] = memorized[7];
cube[3][4] = memorized[4];
cube[3][5] = memorized[1];
}
void u() {
for (int i = 0; i < 3; ++i)
{
U();
}
}
void r() {
for (int i = 0; i < 3; ++i)
{
R();
}
}
void f() {
for (int i = 0; i < 3; ++i)
{
F();
}
}
void d() {
for (int i = 0; i < 3; ++i)
{
D();
}
}
void l(){
for (int i = 0; i < 3; ++i)
{
L();
}
}
void b(){
for (int i = 0; i < 3; ++i)
{
B();
}
}
void x(){
for (int i = 0; i < 3; ++i)
{
X();
}
}
void y(){
for (int i = 0; i < 3; ++i)
{
Y();
}
}
void z(){
for (int i = 0; i < 3; ++i)
{
Z();
}
}
int isValid(){
int r = 1;
for (int i = 0; i < 6; ++i)
{
for (int j = 0; j < 9; ++j)
{
//printf("%d ", cube[i][j]);
if (cube[i][j] != (i+1)*(j+1))
{
r = 0;
//break;
}
}
//printf("\n");
}
return r;
}
int main(){
freopen("data_15.txt","r",stdin);
// 0,1,2,3,4,5
//F(Front),B(Back),U(Up),D(Down):,L(Left),R(Right)
for (int i = 0; i < 6; ++i)
{
for (int j = 0; j < 9; ++j)
{
cube[i][j] = (i+1)*(j+1);
}
}
//R();U();F();D();L();B();X();Y();Z();z();y();x();b();l();d();f();u();r();
char cmd;
while(scanf("%c",&cmd)!=EOF && cmd!='\0') {
switch (cmd) {
case 'U':
U();
break;
case 'R':
R();
break;
case 'F':
F();
break;
case 'D':
D();
break;
case 'L':
L();
break;
case 'B':
B();
break;
case 'X':
X();
break;
case 'Y':
Y();
break;
case 'Z':
Z();
break;
case 'u':
u();
break;
case 'r':
r();
break;
case 'f':
f();
break;
case 'd':
d();
break;
case 'l':
l();
break;
case 'b':
b();
break;
case 'x':
x();
break;
case 'y':
y();
break;
case 'z':
z();
break;
}
}
if (isValid()) {
printf("Yes\n");
} else {
printf("No\n");
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.