魔方

cube.c

// 魔方是一种常见的玩具。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;
}

test_data.in

RUur