루빅스 큐브

실행 시간 10 초 메모리 Heap, Global, Stack 등을 모두 합쳐서 최대 1 GB 까지 사용 가능 (단, Stack 은 최대 1 MB 까지 사용 가능) 제출 횟수 제한 10회 < 주의 사항 > ① 응시자는 User Code 안의 runtest() 함수를 구현해야 한다. ② User Code 안에는 어떠한 헤더 파일도 추가할 수 없다.    ( 단, malloc.h 사용 가능 ) ③ Input 파일은 사용되지 않는다. ④ Main 은 수정할 수 없으며, 실제 채점 시에도 그대로 사용된다.    ( 단, srand(3) 의 파라미터는 변경 ) ⑤ 본 검정은 C++ 언어만 지원한다. ▶ runtest() 함수를 작성하여, SCORE를 최소로 만드시오!   다음과 같이, (면 번호, 각 면의 행, 열) 3차원 배열로 표현된 루빅스 큐브가 있다.                                                                      [Fig. 1] [Fig. 2]는 [Fig. 1]의 전개도를 나타낸다.        [Fig. 2]   F, B, U, D, L, R은 각각 Front(=0), Back(=1), Up(=2), Down(=3), Left(=4), Right(=5)를 나타낸다. 3차원 배열의 값은 색을 나타내며, 초기 값은 면 번호와 같다. Main code에서 10회, 임의의 면을 임의의 방향으로 90°씩 회전시켜 큐브를 섞는다. 큐브를 섞는 동작은 rotate() API를 호출하여 수행하며, User code에서 구현해야 되는 runtest() 함수에서도 동일한 API를 호출하여 초기 상태로 큐브를 맞추어야 한다.   User code에서 구현해야 되는 API는 다음과 같다.   void runtest(int cube[6][3][3])     (면 번호, 각 면의 행, 열) 3차원 배열로 표현된 큐브가 전달된다. 제공되는 rotate() API를 적절히 호출하여, 큐브를 [Fig. 2] 처럼 초기 상태로 맞추어야 한다.     User code에 제공되는 API는 다음과 같다.   void rotate(int face, bool clockwise)     각 입력 값에 따른 동작은 아래 그림을 참조한다. (0 ≤ face ≤ 5)         기타 자세한 사항은 주어진 코드를 분석하여 파악한다.

#define _CRT_SECURE_NO_WARNINGS // Ignore build errors when using unsafe functions in Visual Studio. #include <stdio.h> #include <stdlib.h> #include <time.h> #define CUBE_SIZE 3 #define FRONT 0 #define BACK 1 #define UP 2 #define DOWN 3 #define LEFT 4 #define RIGHT 5 extern void runtest(int cube[6][CUBE_SIZE][CUBE_SIZE]); static int Cube[6][CUBE_SIZE][CUBE_SIZE]; static int CallCnt = 0; void rotate(int face, bool clockwise) { int preCube[6][CUBE_SIZE][CUBE_SIZE]; ++CallCnt; register int s, i, j; for (s = 0; s < 6; ++s) for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) preCube[s][i][j] = Cube[s][i][j]; if (clockwise) { for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j)#define _CRT_SECURE_NO_WARNINGS // Ignore build errors when using unsafe functions in Visual Studio. #include <stdio.h> #include <stdlib.h> #include <time.h> #define CUBE_SIZE 3 #define FRONT 0 #define BACK 1 #define UP 2 #define DOWN 3 #define LEFT 4 #define RIGHT 5 extern void runtest(int cube[6][CUBE_SIZE][CUBE_SIZE]); static int Cube[6][CUBE_SIZE][CUBE_SIZE]; static int CallCnt = 0; void rotate(int face, bool clockwise) { int preCube[6][CUBE_SIZE][CUBE_SIZE]; ++CallCnt; register int s, i, j; for (s = 0; s < 6; ++s) for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) preCube[s][i][j] = Cube[s][i][j]; if (clockwise) { for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) Cube[face][j][CUBE_SIZE - 1 - i] = preCube[face][i][j]; } else { for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) Cube[face][CUBE_SIZE - 1 - j][i] = preCube[face][i][j]; } switch (face) { case FRONT: if (clockwise) { Cube[UP][2][0] = preCube[LEFT][2][2]; Cube[UP][2][1] = preCube[LEFT][1][2]; Cube[UP][2][2] = preCube[LEFT][0][2]; Cube[RIGHT][0][0] = preCube[UP][2][0]; Cube[RIGHT][1][0] = preCube[UP][2][1]; Cube[RIGHT][2][0] = preCube[UP][2][2]; Cube[DOWN][0][0] = preCube[RIGHT][2][0]; Cube[DOWN][0][1] = preCube[RIGHT][1][0]; Cube[DOWN][0][2] = preCube[RIGHT][0][0]; Cube[LEFT][0][2] = preCube[DOWN][0][0]; Cube[LEFT][1][2] = preCube[DOWN][0][1]; Cube[LEFT][2][2] = preCube[DOWN][0][2]; } else { Cube[UP][2][0] = preCube[RIGHT][0][0]; Cube[UP][2][1] = preCube[RIGHT][1][0]; Cube[UP][2][2] = preCube[RIGHT][2][0]; Cube[RIGHT][0][0] = preCube[DOWN][0][2]; Cube[RIGHT][1][0] = preCube[DOWN][0][1]; Cube[RIGHT][2][0] = preCube[DOWN][0][0]; Cube[DOWN][0][0] = preCube[LEFT][0][2]; Cube[DOWN][0][1] = preCube[LEFT][1][2]; Cube[DOWN][0][2] = preCube[LEFT][2][2]; Cube[LEFT][0][2] = preCube[UP][2][2]; Cube[LEFT][1][2] = preCube[UP][2][1]; Cube[LEFT][2][2] = preCube[UP][2][0]; } break; case BACK: if (clockwise) { Cube[UP][0][2] = preCube[RIGHT][2][2]; Cube[UP][0][1] = preCube[RIGHT][1][2]; Cube[UP][0][0] = preCube[RIGHT][0][2]; Cube[LEFT][0][0] = preCube[UP][0][2]; Cube[LEFT][1][0] = preCube[UP][0][1]; Cube[LEFT][2][0] = preCube[UP][0][0]; Cube[DOWN][2][2] = preCube[LEFT][2][0]; Cube[DOWN][2][1] = preCube[LEFT][1][0]; Cube[DOWN][2][0] = preCube[LEFT][0][0]; Cube[RIGHT][0][2] = preCube[DOWN][2][2]; Cube[RIGHT][1][2] = preCube[DOWN][2][1]; Cube[RIGHT][2][2] = preCube[DOWN][2][0]; } else { Cube[UP][0][2] = preCube[LEFT][0][0]; Cube[UP][0][1] = preCube[LEFT][1][0]; Cube[UP][0][0] = preCube[LEFT][2][0]; Cube[LEFT][0][0] = preCube[DOWN][2][0]; Cube[LEFT][1][0] = preCube[DOWN][2][1]; Cube[LEFT][2][0] = preCube[DOWN][2][2]; Cube[DOWN][2][2] = preCube[RIGHT][0][2]; Cube[DOWN][2][1] = preCube[RIGHT][1][2]; Cube[DOWN][2][0] = preCube[RIGHT][2][2]; Cube[RIGHT][0][2] = preCube[UP][0][0]; Cube[RIGHT][1][2] = preCube[UP][0][1]; Cube[RIGHT][2][2] = preCube[UP][0][2]; } break; case UP: if (clockwise) { Cube[BACK][0][2] = preCube[LEFT][0][2]; Cube[BACK][0][1] = preCube[LEFT][0][1]; Cube[BACK][0][0] = preCube[LEFT][0][0]; Cube[RIGHT][0][2] = preCube[BACK][0][2]; Cube[RIGHT][0][1] = preCube[BACK][0][1]; Cube[RIGHT][0][0] = preCube[BACK][0][0]; Cube[FRONT][0][0] = preCube[RIGHT][0][0]; Cube[FRONT][0][1] = preCube[RIGHT][0][1]; Cube[FRONT][0][2] = preCube[RIGHT][0][2]; Cube[LEFT][0][0] = preCube[FRONT][0][0]; Cube[LEFT][0][1] = preCube[FRONT][0][1]; Cube[LEFT][0][2] = preCube[FRONT][0][2]; } else { Cube[BACK][0][2] = preCube[RIGHT][0][2]; Cube[BACK][0][1] = preCube[RIGHT][0][1]; Cube[BACK][0][0] = preCube[RIGHT][0][0]; Cube[RIGHT][0][2] = preCube[FRONT][0][2]; Cube[RIGHT][0][1] = preCube[FRONT][0][1]; Cube[RIGHT][0][0] = preCube[FRONT][0][0]; Cube[FRONT][0][0] = preCube[LEFT][0][0]; Cube[FRONT][0][1] = preCube[LEFT][0][1]; Cube[FRONT][0][2] = preCube[LEFT][0][2]; Cube[LEFT][0][0] = preCube[BACK][0][0]; Cube[LEFT][0][1] = preCube[BACK][0][1]; Cube[LEFT][0][2] = preCube[BACK][0][2]; } break; case DOWN: if (clockwise) { Cube[FRONT][2][0] = preCube[LEFT][2][0]; Cube[FRONT][2][1] = preCube[LEFT][2][1]; Cube[FRONT][2][2] = preCube[LEFT][2][2]; Cube[RIGHT][2][0] = preCube[FRONT][2][0]; Cube[RIGHT][2][1] = preCube[FRONT][2][1]; Cube[RIGHT][2][2] = preCube[FRONT][2][2]; Cube[BACK][2][2] = preCube[RIGHT][2][2]; Cube[BACK][2][1] = preCube[RIGHT][2][1]; Cube[BACK][2][0] = preCube[RIGHT][2][0]; Cube[LEFT][2][2] = preCube[BACK][2][2]; Cube[LEFT][2][1] = preCube[BACK][2][1]; Cube[LEFT][2][0] = preCube[BACK][2][0]; } else { Cube[FRONT][2][0] = preCube[RIGHT][2][0]; Cube[FRONT][2][1] = preCube[RIGHT][2][1]; Cube[FRONT][2][2] = preCube[RIGHT][2][2]; Cube[RIGHT][2][0] = preCube[BACK][2][0]; Cube[RIGHT][2][1] = preCube[BACK][2][1]; Cube[RIGHT][2][2] = preCube[BACK][2][2]; Cube[BACK][2][2] = preCube[LEFT][2][2]; Cube[BACK][2][1] = preCube[LEFT][2][1]; Cube[BACK][2][0] = preCube[LEFT][2][0]; Cube[LEFT][2][2] = preCube[FRONT][2][2]; Cube[LEFT][2][1] = preCube[FRONT][2][1]; Cube[LEFT][2][0] = preCube[FRONT][2][0]; } break; case LEFT: if (clockwise) { Cube[UP][0][0] = preCube[BACK][2][2]; Cube[UP][1][0] = preCube[BACK][1][2]; Cube[UP][2][0] = preCube[BACK][0][2]; Cube[FRONT][0][0] = preCube[UP][0][0]; Cube[FRONT][1][0] = preCube[UP][1][0]; Cube[FRONT][2][0] = preCube[UP][2][0]; Cube[DOWN][2][0] = preCube[FRONT][2][0]; Cube[DOWN][1][0] = preCube[FRONT][1][0]; Cube[DOWN][0][0] = preCube[FRONT][0][0]; Cube[BACK][0][2] = preCube[DOWN][2][0]; Cube[BACK][1][2] = preCube[DOWN][1][0]; Cube[BACK][2][2] = preCube[DOWN][0][0]; } else { Cube[UP][0][0] = preCube[FRONT][0][0]; Cube[UP][1][0] = preCube[FRONT][1][0]; Cube[UP][2][0] = preCube[FRONT][2][0]; Cube[FRONT][0][0] = preCube[DOWN][0][0]; Cube[FRONT][1][0] = preCube[DOWN][1][0]; Cube[FRONT][2][0] = preCube[DOWN][2][0]; Cube[DOWN][2][0] = preCube[BACK][0][2]; Cube[DOWN][1][0] = preCube[BACK][1][2]; Cube[DOWN][0][0] = preCube[BACK][2][2]; Cube[BACK][0][2] = preCube[UP][2][0]; Cube[BACK][1][2] = preCube[UP][1][0]; Cube[BACK][2][2] = preCube[UP][0][0]; } break; case RIGHT: if (clockwise) { Cube[UP][2][2] = preCube[FRONT][2][2]; Cube[UP][1][2] = preCube[FRONT][1][2]; Cube[UP][0][2] = preCube[FRONT][0][2]; Cube[BACK][0][0] = preCube[UP][2][2]; Cube[BACK][1][0] = preCube[UP][1][2]; Cube[BACK][2][0] = preCube[UP][0][2]; Cube[DOWN][0][2] = preCube[BACK][2][0]; Cube[DOWN][1][2] = preCube[BACK][1][0]; Cube[DOWN][2][2] = preCube[BACK][0][0]; Cube[FRONT][0][2] = preCube[DOWN][0][2]; Cube[FRONT][1][2] = preCube[DOWN][1][2]; Cube[FRONT][2][2] = preCube[DOWN][2][2]; } else { Cube[UP][2][2] = preCube[BACK][0][0]; Cube[UP][1][2] = preCube[BACK][1][0]; Cube[UP][0][2] = preCube[BACK][2][0]; Cube[BACK][0][0] = preCube[DOWN][2][2]; Cube[BACK][1][0] = preCube[DOWN][1][2]; Cube[BACK][2][0] = preCube[DOWN][0][2]; Cube[DOWN][0][2] = preCube[FRONT][0][2]; Cube[DOWN][1][2] = preCube[FRONT][1][2]; Cube[DOWN][2][2] = preCube[FRONT][2][2]; Cube[FRONT][0][2] = preCube[UP][0][2]; Cube[FRONT][1][2] = preCube[UP][1][2]; Cube[FRONT][2][2] = preCube[UP][2][2]; } break; } } int main(void) { setbuf(stdout, NULL); srand(3); // The seed will be changed. int testCnt = 20; double totalCallCnt = 0.0; double totalRunTime = 0.0; for (int tc = 1; tc <= testCnt; ++tc) { int arr[6][CUBE_SIZE][CUBE_SIZE]; register int face, row, col; for (face = 0; face < 6; ++face) for (row = 0; row < CUBE_SIZE; ++row) for (col = 0; col < CUBE_SIZE; ++col) Cube[face][row][col] = face; for (register int cnt = 0; cnt < 10; ++cnt) { int s = rand() % 6; bool c = rand() % 2 ? true : false; rotate(s, c); } for (face = 0; face < 6; ++face) for (row = 0; row < CUBE_SIZE; ++row) for (col = 0; col < CUBE_SIZE; ++col) arr[face][row][col] = Cube[face][row][col]; CallCnt = 0; time_t start = clock(); runtest(arr); totalRunTime += (clock() - start) / (CLOCKS_PER_SEC / 1000); for (face = 0; face < 6; ++face) for (row = 0; row < CUBE_SIZE; ++row) for (col = 0; col < CUBE_SIZE; ++col) if (Cube[face][row][col] != face) CallCnt += 1000; printf("#%d %d\n", tc, CallCnt); totalCallCnt += CallCnt; } printf("SCORE: %.4lf\n", totalCallCnt + totalRunTime / 10000); return 0; } Cube[face][j][CUBE_SIZE - 1 - i] = preCube[face][i][j]; } else { for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) Cube[face][CUBE_SIZE - 1 - j][i] = preCube[face][i][j]; } switch (face) { case FRONT: if (clockwise) { Cube[UP][2][0] = preCube[LEFT][2][2]; Cube[UP][2][1] = preCube[LEFT][1][2]; Cube[UP][2][2] = preCube[LEFT][0][2]; Cube[RIGHT][0][0] = preCube[UP][2][0]; Cube[RIGHT][1][0] = preCube[UP][2][1]; Cube[RIGHT][2][0] = preCube[UP][2][2]; Cube[DOWN][0][0] = preCube[RIGHT][2][0]; Cube[DOWN][0][1] = preCube[RIGHT][1][0]; Cube[DOWN][0][2] = preCube[RIGHT][0][0]; Cube[LEFT][0][2] = preCube[DOWN][0][0]; Cube[LEFT][1][2] = preCube[DOWN][0][1]; Cube[LEFT][2][2] = preCube[DOWN][0][2]; } else { Cube[UP][2][0] = preCube[RIGHT][0][0]; Cube[UP][2][1] = preCube[RIGHT][1][0]; Cube[UP][2][2] = preCube[RIGHT][2][0]; Cube[RIGHT][0][0] = preCube[DOWN][0][2]; Cube[RIGHT][1][0] = preCube[DOWN][0][1]; Cube[RIGHT][2][0] = preCube[DOWN][0][0]; Cube[DOWN][0][0] = preCube[LEFT][0][2]; Cube[DOWN][0][1] = preCube[LEFT][1][2]; Cube[DOWN][0][2] = preCube[LEFT][2][2]; Cube[LEFT][0][2] = preCube[UP][2][2]; Cube[LEFT][1][2] = preCube[UP][2][1]; Cube[LEFT][2][2] = preCube[UP][2][0]; } break; case BACK: if (clockwise) { Cube[UP][0][2] = preCube[RIGHT][2][2]; Cube[UP][0][1] = preCube[RIGHT][1][2]; Cube[UP][0][0] = preCube[RIGHT][0][2]; Cube[LEFT][0][0] = preCube[UP][0][2]; Cube[LEFT][1][0] = preCube[UP][0][1]; Cube[LEFT][2][0] = preCube[UP][0][0]; Cube[DOWN][2][2] = preCube[LEFT][2][0]; Cube[DOWN][2][1] = preCube[LEFT][1][0]; Cube[DOWN][2][0] = preCube[LEFT][0][0]; Cube[RIGHT][0][2] = preCube[DOWN][2][2]; Cube[RIGHT][1][2] = preCube[DOWN][2][1]; Cube[RIGHT][2][2] = preCube[DOWN][2][0]; } else { Cube[UP][0][2] = preCube[LEFT][0][0]; Cube[UP][0][1] = preCube[LEFT][1][0]; Cube[UP][0][0] = preCube[LEFT][2][0]; Cube[LEFT][0][0] = preCube[DOWN][2][0]; Cube[LEFT][1][0] = preCube[DOWN][2][1]; Cube[LEFT][2][0] = preCube[DOWN][2][2]; Cube[DOWN][2][2] = preCube[RIGHT][0][2]; Cube[DOWN][2][1] = preCube[RIGHT][1][2]; Cube[DOWN][2][0] = preCube[RIGHT][2][2]; Cube[RIGHT][0][2] = preCube[UP][0][0]; Cube[RIGHT][1][2] = preCube[UP][0][1]; Cube[RIGHT][2][2] = preCube[UP][0][2]; } break; case UP: if (clockwise) { Cube[BACK][0][2] = preCube[LEFT][0][2]; Cube[BACK][0][1] = preCube[LEFT][0][1]; Cube[BACK][0][0] = preCube[LEFT][0][0]; Cube[RIGHT][0][2] = preCube[BACK][0][2]; Cube[RIGHT][0][1] = preCube[BACK][0][1]; Cube[RIGHT][0][0] = preCube[BACK][0][0]; Cube[FRONT][0][0] = preCube[RIGHT][0][0]; Cube[FRONT][0][1] = preCube[RIGHT][0][1]; Cube[FRONT][0][2] = preCube[RIGHT][0][2]; Cube[LEFT][0][0] = preCube[FRONT][0][0]; Cube[LEFT][0][1] = preCube[FRONT][0][1]; Cube[LEFT][0][2] = preCube[FRONT][0][2]; } else { Cube[BACK][0][2] = preCube[RIGHT][0][2]; Cube[BACK][0][1] = preCube[RIGHT][0][1]; Cube[BACK][0][0] = preCube[RIGHT][0][0]; Cube[RIGHT][0][2] = preCube[FRONT][0][2]; Cube[RIGHT][0][1] = preCube[FRONT][0][1]; Cube[RIGHT][0][0] = preCube[FRONT][0][0]; Cube[FRONT][0][0] = preCube[LEFT][0][0]; Cube[FRONT][0][1] = preCube[LEFT][0][1]; Cube[FRONT][0][2] = preCube[LEFT][0][2]; Cube[LEFT][0][0] = preCube[BACK][0][0]; Cube[LEFT][0][1] = preCube[BACK][0][1]; Cube[LEFT][0][2] = preCube[BACK][0][2]; } break; case DOWN: if (clockwise) { Cube[FRONT][2][0] = preCube[LEFT][2][0]; Cube[FRONT][2][1] = preCube[LEFT][2][1]; Cube[FRONT][2][2] = preCube[LEFT][2][2]; Cube[RIGHT][2][0] = preCube[FRONT][2][0]; Cube[RIGHT][2][1] = preCube[FRONT][2][1]; Cube[RIGHT][2][2] = preCube[FRONT][2][2]; Cube[BACK][2][2] = preCube[RIGHT][2][2]; Cube[BACK][2][1] = preCube[RIGHT][2][1]; Cube[BACK][2][0] = preCube[RIGHT][2][0]; Cube[LEFT][2][2] = preCube[BACK][2][2]; Cube[LEFT][2][1] = preCube[BACK][2][1]; Cube[LEFT][2][0] = preCube[BACK][2][0]; } else { Cube[FRONT][2][0] = preCube[RIGHT][2][0]; Cube[FRONT][2][1] = preCube[RIGHT][2][1]; Cube[FRONT][2][2] = preCube[RIGHT][2][2]; Cube[RIGHT][2][0] = preCube[BACK][2][0]; Cube[RIGHT][2][1] = preCube[BACK][2][1]; Cube[RIGHT][2][2] = preCube[BACK][2][2]; Cube[BACK][2][2] = preCube[LEFT][2][2]; Cube[BACK][2][1] = preCube[LEFT][2][1]; Cube[BACK][2][0] = preCube[LEFT][2][0]; Cube[LEFT][2][2] = preCube[FRONT][2][2]; Cube[LEFT][2][1] = preCube[FRONT][2][1]; Cube[LEFT][2][0] = preCube[FRONT][2][0]; } break; case LEFT: if (clockwise) { Cube[UP][0][0] = preCube[BACK][2][2]; Cube[UP][1][0] = preCube[BACK][1][2]; Cube[UP][2][0] = preCube[BACK][0][2]; Cube[FRONT][0][0] = preCube[UP][0][0]; Cube[FRONT][1][0] = preCube[UP][1][0]; Cube[FRONT][2][0] = preCube[UP][2][0]; Cube[DOWN][2][0] = preCube[FRONT][2][0]; Cube[DOWN][1][0] = preCube[FRONT][1][0]; Cube[DOWN][0][0] = preCube[FRONT][0][0]; Cube[BACK][0][2] = preCube[DOWN][2][0]; Cube[BACK][1][2] = preCube[DOWN][1][0]; Cube[BACK][2][2] = preCube[DOWN][0][0]; } else { Cube[UP][0][0] = preCube[FRONT][0][0]; Cube[UP][1][0] = preCube[FRONT][1][0]; Cube[UP][2][0] = preCube[FRONT][2][0]; Cube[FRONT][0][0] = preCube[DOWN][0][0]; Cube[FRONT][1][0] = preCube[DOWN][1][0]; Cube[FRONT][2][0] = preCube[DOWN][2][0]; Cube[DOWN][2][0] = preCube[BACK][0][2]; Cube[DOWN][1][0] = preCube[BACK][1][2]; Cube[DOWN][0][0] = preCube[BACK][2][2]; Cube[BACK][0][2] = preCube[UP][2][0]; Cube[BACK][1][2] = preCube[UP][1][0]; Cube[BACK][2][2] = preCube[UP][0][0]; } break; case RIGHT: if (clockwise) { Cube[UP][2][2] = preCube[FRONT][2][2]; Cube[UP][1][2] = preCube[FRONT][1][2]; Cube[UP][0][2] = preCube[FRONT][0][2]; Cube[BACK][0][0] = preCube[UP][2][2]; Cube[BACK][1][0] = preCube[UP][1][2]; Cube[BACK][2][0] = preCube[UP][0][2]; Cube[DOWN][0][2] = preCube[BACK][2][0]; Cube[DOWN][1][2] = preCube[BACK][1][0]; Cube[DOWN][2][2] = preCube[BACK][0][0]; Cube[FRONT][0][2] = preCube[DOWN][0][2]; Cube[FRONT][1][2] = preCube[DOWN][1][2]; Cube[FRONT][2][2] = preCube[DOWN][2][2]; } else { Cube[UP][2][2] = preCube[BACK][0][0]; Cube[UP][1][2] = preCube[BACK][1][0]; Cube[UP][0][2] = preCube[BACK][2][0]; Cube[BACK][0][0] = preCube[DOWN][2][2]; Cube[BACK][1][0] = preCube[DOWN][1][2]; Cube[BACK][2][0] = preCube[DOWN][0][2]; Cube[DOWN][0][2] = preCube[FRONT][0][2]; Cube[DOWN][1][2] = preCube[FRONT][1][2]; Cube[DOWN][2][2] = preCube[FRONT][2][2]; Cube[FRONT][0][2] = preCube[UP][0][2]; Cube[FRONT][1][2] = preCube[UP][1][2]; Cube[FRONT][2][2] = preCube[UP][2][2]; } break; } } int main(void) { setbuf(stdout, NULL); srand(3); // The seed will be changed. int testCnt = 20; double totalCallCnt = 0.0; double totalRunTime = 0.0; for (int tc = 1; tc <= testCnt; ++tc) { int arr[6][CUBE_SIZE][CUBE_SIZE]; register int face, row, col; for (face = 0; face < 6; ++face) for (row = 0; row < CUBE_SIZE; ++row) for (col = 0; col < CUBE_SIZE; ++col) Cube[face][row][col] = face; for (register int cnt = 0; cnt < 10; ++cnt) { int s = rand() % 6; bool c = rand() % 2 ? true : false; rotate(s, c); } for (face = 0; face < 6; ++face) for (row = 0; row < CUBE_SIZE; ++row) for (col = 0; col < CUBE_SIZE; ++col) arr[face][row][col] = Cube[face][row][col]; CallCnt = 0; time_t start = clock(); runtest(arr); totalRunTime += (clock() - start) / (CLOCKS_PER_SEC / 1000); for (face = 0; face < 6; ++face) for (row = 0; row < CUBE_SIZE; ++row) for (col = 0; col < CUBE_SIZE; ++col) if (Cube[face][row][col] != face) CallCnt += 1000; printf("#%d %d\n", tc, CallCnt); totalCallCnt += CallCnt; } printf("SCORE: %.4lf\n", totalCallCnt + totalRunTime / 10000); return 0; }

#define CUBE_SIZE 3 #define FRONT 0 #define BACK 1 #define UP 2 #define DOWN 3 #define LEFT 4 #define RIGHT 5 #define CUBE_LENGTH 54 extern void rotate(int face, bool clockwise); int cnt; int minSumDepth = 10; int minRotation[10]; int myCube[6][CUBE_SIZE][CUBE_SIZE]; void rotateTest(int Cube[6][CUBE_SIZE][CUBE_SIZE], int face, bool clockwise) { int preCube[6][CUBE_SIZE][CUBE_SIZE]; register int s, i, j; for (s = 0; s < 6; ++s) for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) preCube[s][i][j] = Cube[s][i][j]; if (clockwise) { for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) Cube[face][j][CUBE_SIZE - 1 - i] = preCube[face][i][j]; } else { for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) Cube[face][CUBE_SIZE - 1 - j][i] = preCube[face][i][j]; } switch (face) { case FRONT: if (clockwise) { Cube[UP][2][0] = preCube[LEFT][2][2]; Cube[UP][2][1] = preCube[LEFT][1][2]; Cube[UP][2][2] = preCube[LEFT][0][2]; Cube[RIGHT][0][0] = preCube[UP][2][0]; Cube[RIGHT][1][0] = preCube[UP][2][1]; Cube[RIGHT][2][0] = preCube[UP][2][2]; Cube[DOWN][0][0] = preCube[RIGHT][2][0]; Cube[DOWN][0][1] = preCube[RIGHT][1][0]; Cube[DOWN][0][2] = preCube[RIGHT][0][0]; Cube[LEFT][0][2] = preCube[DOWN][0][0]; Cube[LEFT][1][2] = preCube[DOWN][0][1]; Cube[LEFT][2][2] = preCube[DOWN][0][2]; } else { Cube[UP][2][0] = preCube[RIGHT][0][0]; Cube[UP][2][1] = preCube[RIGHT][1][0]; Cube[UP][2][2] = preCube[RIGHT][2][0]; Cube[RIGHT][0][0] = preCube[DOWN][0][2]; Cube[RIGHT][1][0] = preCube[DOWN][0][1]; Cube[RIGHT][2][0] = preCube[DOWN][0][0]; Cube[DOWN][0][0] = preCube[LEFT][0][2]; Cube[DOWN][0][1] = preCube[LEFT][1][2]; Cube[DOWN][0][2] = preCube[LEFT][2][2]; Cube[LEFT][0][2] = preCube[UP][2][2]; Cube[LEFT][1][2] = preCube[UP][2][1]; Cube[LEFT][2][2] = preCube[UP][2][0]; } break; case BACK: if (clockwise) { Cube[UP][0][2] = preCube[RIGHT][2][2]; Cube[UP][0][1] = preCube[RIGHT][1][2]; Cube[UP][0][0] = preCube[RIGHT][0][2]; Cube[LEFT][0][0] = preCube[UP][0][2]; Cube[LEFT][1][0] = preCube[UP][0][1]; Cube[LEFT][2][0] = preCube[UP][0][0]; Cube[DOWN][2][2] = preCube[LEFT][2][0]; Cube[DOWN][2][1] = preCube[LEFT][1][0]; Cube[DOWN][2][0] = preCube[LEFT][0][0]; Cube[RIGHT][0][2] = preCube[DOWN][2][2]; Cube[RIGHT][1][2] = preCube[DOWN][2][1]; Cube[RIGHT][2][2] = preCube[DOWN][2][0]; } else { Cube[UP][0][2] = preCube[LEFT][0][0]; Cube[UP][0][1] = preCube[LEFT][1][0]; Cube[UP][0][0] = preCube[LEFT][2][0]; Cube[LEFT][0][0] = preCube[DOWN][2][0]; Cube[LEFT][1][0] = preCube[DOWN][2][1]; Cube[LEFT][2][0] = preCube[DOWN][2][2]; Cube[DOWN][2][2] = preCube[RIGHT][0][2]; Cube[DOWN][2][1] = preCube[RIGHT][1][2]; Cube[DOWN][2][0] = preCube[RIGHT][2][2]; Cube[RIGHT][0][2] = preCube[UP][0][0]; Cube[RIGHT][1][2] = preCube[UP][0][1]; Cube[RIGHT][2][2] = preCube[UP][0][2]; } break; case UP: if (clockwise) { Cube[BACK][0][2] = preCube[LEFT][0][2]; Cube[BACK][0][1] = preCube[LEFT][0][1]; Cube[BACK][0][0] = preCube[LEFT][0][0]; Cube[RIGHT][0][2] = preCube[BACK][0][2]; Cube[RIGHT][0][1] = preCube[BACK][0][1]; Cube[RIGHT][0][0] = preCube[BACK][0][0]; Cube[FRONT][0][0] = preCube[RIGHT][0][0]; Cube[FRONT][0][1] = preCube[RIGHT][0][1]; Cube[FRONT][0][2] = preCube[RIGHT][0][2]; Cube[LEFT][0][0] = preCube[FRONT][0][0]; Cube[LEFT][0][1] = preCube[FRONT][0][1]; Cube[LEFT][0][2] = preCube[FRONT][0][2]; } else { Cube[BACK][0][2] = preCube[RIGHT][0][2]; Cube[BACK][0][1] = preCube[RIGHT][0][1]; Cube[BACK][0][0] = preCube[RIGHT][0][0]; Cube[RIGHT][0][2] = preCube[FRONT][0][2]; Cube[RIGHT][0][1] = preCube[FRONT][0][1]; Cube[RIGHT][0][0] = preCube[FRONT][0][0]; Cube[FRONT][0][0] = preCube[LEFT][0][0]; Cube[FRONT][0][1] = preCube[LEFT][0][1]; Cube[FRONT][0][2] = preCube[LEFT][0][2]; Cube[LEFT][0][0] = preCube[BACK][0][0]; Cube[LEFT][0][1] = preCube[BACK][0][1]; Cube[LEFT][0][2] = preCube[BACK][0][2]; } break; case DOWN: if (clockwise) { Cube[FRONT][2][0] = preCube[LEFT][2][0]; Cube[FRONT][2][1] = preCube[LEFT][2][1]; Cube[FRONT][2][2] = preCube[LEFT][2][2]; Cube[RIGHT][2][0] = preCube[FRONT][2][0]; Cube[RIGHT][2][1] = preCube[FRONT][2][1]; Cube[RIGHT][2][2] = preCube[FRONT][2][2]; Cube[BACK][2][2] = preCube[RIGHT][2][2]; Cube[BACK][2][1] = preCube[RIGHT][2][1]; Cube[BACK][2][0] = preCube[RIGHT][2][0]; Cube[LEFT][2][2] = preCube[BACK][2][2]; Cube[LEFT][2][1] = preCube[BACK][2][1]; Cube[LEFT][2][0] = preCube[BACK][2][0]; } else { Cube[FRONT][2][0] = preCube[RIGHT][2][0]; Cube[FRONT][2][1] = preCube[RIGHT][2][1]; Cube[FRONT][2][2] = preCube[RIGHT][2][2]; Cube[RIGHT][2][0] = preCube[BACK][2][0]; Cube[RIGHT][2][1] = preCube[BACK][2][1]; Cube[RIGHT][2][2] = preCube[BACK][2][2]; Cube[BACK][2][2] = preCube[LEFT][2][2]; Cube[BACK][2][1] = preCube[LEFT][2][1]; Cube[BACK][2][0] = preCube[LEFT][2][0]; Cube[LEFT][2][2] = preCube[FRONT][2][2]; Cube[LEFT][2][1] = preCube[FRONT][2][1]; Cube[LEFT][2][0] = preCube[FRONT][2][0]; } break; case LEFT: if (clockwise) { Cube[UP][0][0] = preCube[BACK][2][2]; Cube[UP][1][0] = preCube[BACK][1][2]; Cube[UP][2][0] = preCube[BACK][0][2]; Cube[FRONT][0][0] = preCube[UP][0][0]; Cube[FRONT][1][0] = preCube[UP][1][0]; Cube[FRONT][2][0] = preCube[UP][2][0]; Cube[DOWN][2][0] = preCube[FRONT][2][0]; Cube[DOWN][1][0] = preCube[FRONT][1][0]; Cube[DOWN][0][0] = preCube[FRONT][0][0]; Cube[BACK][0][2] = preCube[DOWN][2][0]; Cube[BACK][1][2] = preCube[DOWN][1][0]; Cube[BACK][2][2] = preCube[DOWN][0][0]; } else { Cube[UP][0][0] = preCube[FRONT][0][0]; Cube[UP][1][0] = preCube[FRONT][1][0]; Cube[UP][2][0] = preCube[FRONT][2][0]; Cube[FRONT][0][0] = preCube[DOWN][0][0]; Cube[FRONT][1][0] = preCube[DOWN][1][0]; Cube[FRONT][2][0] = preCube[DOWN][2][0]; Cube[DOWN][2][0] = preCube[BACK][0][2]; Cube[DOWN][1][0] = preCube[BACK][1][2]; Cube[DOWN][0][0] = preCube[BACK][2][2]; Cube[BACK][0][2] = preCube[UP][2][0]; Cube[BACK][1][2] = preCube[UP][1][0]; Cube[BACK][2][2] = preCube[UP][0][0]; } break; case RIGHT: if (clockwise) { Cube[UP][2][2] = preCube[FRONT][2][2]; Cube[UP][1][2] = preCube[FRONT][1][2]; Cube[UP][0][2] = preCube[FRONT][0][2]; Cube[BACK][0][0] = preCube[UP][2][2]; Cube[BACK][1][0] = preCube[UP][1][2]; Cube[BACK][2][0] = preCube[UP][0][2]; Cube[DOWN][0][2] = preCube[BACK][2][0]; Cube[DOWN][1][2] = preCube[BACK][1][0]; Cube[DOWN][2][2] = preCube[BACK][0][0]; Cube[FRONT][0][2] = preCube[DOWN][0][2]; Cube[FRONT][1][2] = preCube[DOWN][1][2]; Cube[FRONT][2][2] = preCube[DOWN][2][2]; } else { Cube[UP][2][2] = preCube[BACK][0][0]; Cube[UP][1][2] = preCube[BACK][1][0]; Cube[UP][0][2] = preCube[BACK][2][0]; Cube[BACK][0][0] = preCube[DOWN][2][2]; Cube[BACK][1][0] = preCube[DOWN][1][2]; Cube[BACK][2][0] = preCube[DOWN][0][2]; Cube[DOWN][0][2] = preCube[FRONT][0][2]; Cube[DOWN][1][2] = preCube[FRONT][1][2]; Cube[DOWN][2][2] = preCube[FRONT][2][2]; Cube[FRONT][0][2] = preCube[UP][0][2]; Cube[FRONT][1][2] = preCube[UP][1][2]; Cube[FRONT][2][2] = preCube[UP][2][2]; } break; } } void cubeCpy(int from[6][CUBE_SIZE][CUBE_SIZE], int to[6][CUBE_SIZE][CUBE_SIZE]) { for (int i = 0; i < 6; i++) { for (int j = 0; j < CUBE_SIZE; j++) { for (int k = 0; k < CUBE_SIZE; k++) { to[i][j][k] = from[i][j][k]; } } } } struct CubeHash { char cube[CUBE_LENGTH]; int rotation[5]; int depth; }; #define MAX_TABLE 320000 CubeHash tb[MAX_TABLE]; unsigned long hash(const char key[CUBE_LENGTH]) { unsigned long hash = 5381; for (int i = 0; i < CUBE_LENGTH; i++) { hash = (((hash << 5) + hash) + key[i]) % MAX_TABLE; } return hash % MAX_TABLE; } void initHash() { for (int i = 0; i < MAX_TABLE; i++) { tb[i].depth = -1; } } int keyCmp(const char a[CUBE_LENGTH], const char b[CUBE_LENGTH]) { for (int i = 0; i < CUBE_LENGTH; i++) { if (a[i] != b[i]) { return false; } } return true; } int find(const char key[CUBE_LENGTH]) { unsigned long h = hash(key); int cnt = MAX_TABLE; int step = 1; while (tb[h].depth != -1 && cnt--) { if (keyCmp(tb[h].cube, key)) { return h; } h = (h + 1) % MAX_TABLE; step++; } return -1; } void add(CubeHash ch) { unsigned long h = hash(ch.cube); int step = 1; int i = 0; while (tb[h].depth != -1) { if (keyCmp(tb[h].cube, ch.cube)) { if (tb[h].depth > ch.depth) { tb[h] = ch; } return; } h = (h + 1) % MAX_TABLE; step++; } cnt++; tb[h] = ch; return; } void initCube(int cube[6][CUBE_SIZE][CUBE_SIZE]) { for (int i = 0; i < 6; i++) { for (int j = 0; j < CUBE_SIZE; j++) { for (int k = 0; k < CUBE_SIZE; k++) { cube[i][j][k] = i; } } } } void dfs(int currD, int maxD, int rotation[5]) { if (currD == maxD) { int cube[6][CUBE_SIZE][CUBE_SIZE]; initCube(cube); for (int i = 0; i < maxD; i++) { rotateTest(cube, rotation[i] / 2, rotation[i] % 2); } CubeHash ch; int cubeCurr = 0; for (int i = 0; i < 6; i++) { for (int j = 0; j < CUBE_SIZE; j++) { for (int k = 0; k < CUBE_SIZE; k++) { ch.cube[cubeCurr++] = cube[i][j][k]; } } } for (int i = 0; i < maxD; i++) { ch.rotation[i] = rotation[i]; } ch.depth = maxD; add(ch); return; } for (int i = 0; i < 12; i++) { rotation[currD] = i; dfs(currD + 1, maxD, rotation); } } void dfs2(int currD, int maxD, int rotation[5]) { if (currD == maxD) { int cube[6][CUBE_SIZE][CUBE_SIZE]; cubeCpy(myCube, cube); for (int i = 0; i < maxD; i++) { rotateTest(cube, rotation[i] / 2, rotation[i] % 2); } char strCube[CUBE_LENGTH]; int cubeCurr = 0; for (int i = 0; i < 6; i++) { for (int j = 0; j < CUBE_SIZE; j++) { for (int k = 0; k < CUBE_SIZE; k++) { strCube[cubeCurr++] = cube[i][j][k]; } } } int idx = find(strCube); if (idx != -1) { int newSumDepth = tb[idx].depth + maxD; if (newSumDepth < minSumDepth) { for (int i = 0; i < maxD; i++) { minRotation[i] = rotation[i]; } for (int i = 0; i < tb[idx].depth; i++) { minRotation[newSumDepth - 1 - i] = tb[idx].rotation[i] + (tb[idx].rotation[i] % 2 ? -1 : 1); } minSumDepth = newSumDepth; } } return; } for (int i = 0; i < 12; i++) { rotation[currD] = i; dfs2(currD + 1, maxD, rotation); } } void fillTable() { int defaultCube[6][CUBE_SIZE][CUBE_SIZE]; initHash(); for (int i = 0; i < 6; i++) { for (int j = 0; j < CUBE_SIZE; j++) { for (int k = 0; k < CUBE_SIZE; k++) { defaultCube[i][j][k] = i; } } } int rot[5] = { 0, }; for (int d = 1; d <= 5; d++) { dfs(0, d, rot); } } void findMinRotation() { int rot[5] = { 0, }; for (int d = 0; d <= 5; d++) { dfs2(0, d, rot); } } void runtest(int cube[6][CUBE_SIZE][CUBE_SIZE]) { cubeCpy(cube, myCube); fillTable(); minSumDepth = 11; findMinRotation(); for (int i = 0; i < minSumDepth; i++) { rotate(minRotation[i] / 2, minRotation[i] % 2); } }

#define CUBE_SIZE 3 #define FRONT 0 #define BACK 1 #define UP 2 #define DOWN 3 #define LEFT 4 #define RIGHT 5 #define MAX_KEY 54 #define MAX_TABLE 271453 extern void rotate(int face, bool clockwise); void rotateForSolve(int Cube[6][CUBE_SIZE][CUBE_SIZE], int face, bool clockwise) { int preCube[6][CUBE_SIZE][CUBE_SIZE]; register int s, i, j; for (s = 0; s < 6; ++s) for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) preCube[s][i][j] = Cube[s][i][j]; if (clockwise) { for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) Cube[face][j][CUBE_SIZE - 1 - i] = preCube[face][i][j]; } else { for (i = 0; i < CUBE_SIZE; ++i) for (j = 0; j < CUBE_SIZE; ++j) Cube[face][CUBE_SIZE - 1 - j][i] = preCube[face][i][j]; } switch (face) { case FRONT: if (clockwise) { Cube[UP][2][0] = preCube[LEFT][2][2]; Cube[UP][2][1] = preCube[LEFT][1][2]; Cube[UP][2][2] = preCube[LEFT][0][2]; Cube[RIGHT][0][0] = preCube[UP][2][0]; Cube[RIGHT][1][0] = preCube[UP][2][1]; Cube[RIGHT][2][0] = preCube[UP][2][2]; Cube[DOWN][0][0] = preCube[RIGHT][2][0]; Cube[DOWN][0][1] = preCube[RIGHT][1][0]; Cube[DOWN][0][2] = preCube[RIGHT][0][0]; Cube[LEFT][0][2] = preCube[DOWN][0][0]; Cube[LEFT][1][2] = preCube[DOWN][0][1]; Cube[LEFT][2][2] = preCube[DOWN][0][2]; } else { Cube[UP][2][0] = preCube[RIGHT][0][0]; Cube[UP][2][1] = preCube[RIGHT][1][0]; Cube[UP][2][2] = preCube[RIGHT][2][0]; Cube[RIGHT][0][0] = preCube[DOWN][0][2]; Cube[RIGHT][1][0] = preCube[DOWN][0][1]; Cube[RIGHT][2][0] = preCube[DOWN][0][0]; Cube[DOWN][0][0] = preCube[LEFT][0][2]; Cube[DOWN][0][1] = preCube[LEFT][1][2]; Cube[DOWN][0][2] = preCube[LEFT][2][2]; Cube[LEFT][0][2] = preCube[UP][2][2]; Cube[LEFT][1][2] = preCube[UP][2][1]; Cube[LEFT][2][2] = preCube[UP][2][0]; } break; case BACK: if (clockwise) { Cube[UP][0][2] = preCube[RIGHT][2][2]; Cube[UP][0][1] = preCube[RIGHT][1][2]; Cube[UP][0][0] = preCube[RIGHT][0][2]; Cube[LEFT][0][0] = preCube[UP][0][2]; Cube[LEFT][1][0] = preCube[UP][0][1]; Cube[LEFT][2][0] = preCube[UP][0][0]; Cube[DOWN][2][2] = preCube[LEFT][2][0]; Cube[DOWN][2][1] = preCube[LEFT][1][0]; Cube[DOWN][2][0] = preCube[LEFT][0][0]; Cube[RIGHT][0][2] = preCube[DOWN][2][2]; Cube[RIGHT][1][2] = preCube[DOWN][2][1]; Cube[RIGHT][2][2] = preCube[DOWN][2][0]; } else { Cube[UP][0][2] = preCube[LEFT][0][0]; Cube[UP][0][1] = preCube[LEFT][1][0]; Cube[UP][0][0] = preCube[LEFT][2][0]; Cube[LEFT][0][0] = preCube[DOWN][2][0]; Cube[LEFT][1][0] = preCube[DOWN][2][1]; Cube[LEFT][2][0] = preCube[DOWN][2][2]; Cube[DOWN][2][2] = preCube[RIGHT][0][2]; Cube[DOWN][2][1] = preCube[RIGHT][1][2]; Cube[DOWN][2][0] = preCube[RIGHT][2][2]; Cube[RIGHT][0][2] = preCube[UP][0][0]; Cube[RIGHT][1][2] = preCube[UP][0][1]; Cube[RIGHT][2][2] = preCube[UP][0][2]; } break; case UP: if (clockwise) { Cube[BACK][0][2] = preCube[LEFT][0][2]; Cube[BACK][0][1] = preCube[LEFT][0][1]; Cube[BACK][0][0] = preCube[LEFT][0][0]; Cube[RIGHT][0][2] = preCube[BACK][0][2]; Cube[RIGHT][0][1] = preCube[BACK][0][1]; Cube[RIGHT][0][0] = preCube[BACK][0][0]; Cube[FRONT][0][0] = preCube[RIGHT][0][0]; Cube[FRONT][0][1] = preCube[RIGHT][0][1]; Cube[FRONT][0][2] = preCube[RIGHT][0][2]; Cube[LEFT][0][0] = preCube[FRONT][0][0]; Cube[LEFT][0][1] = preCube[FRONT][0][1]; Cube[LEFT][0][2] = preCube[FRONT][0][2]; } else { Cube[BACK][0][2] = preCube[RIGHT][0][2]; Cube[BACK][0][1] = preCube[RIGHT][0][1]; Cube[BACK][0][0] = preCube[RIGHT][0][0]; Cube[RIGHT][0][2] = preCube[FRONT][0][2]; Cube[RIGHT][0][1] = preCube[FRONT][0][1]; Cube[RIGHT][0][0] = preCube[FRONT][0][0]; Cube[FRONT][0][0] = preCube[LEFT][0][0]; Cube[FRONT][0][1] = preCube[LEFT][0][1]; Cube[FRONT][0][2] = preCube[LEFT][0][2]; Cube[LEFT][0][0] = preCube[BACK][0][0]; Cube[LEFT][0][1] = preCube[BACK][0][1]; Cube[LEFT][0][2] = preCube[BACK][0][2]; } break; case DOWN: if (clockwise) { Cube[FRONT][2][0] = preCube[LEFT][2][0]; Cube[FRONT][2][1] = preCube[LEFT][2][1]; Cube[FRONT][2][2] = preCube[LEFT][2][2]; Cube[RIGHT][2][0] = preCube[FRONT][2][0]; Cube[RIGHT][2][1] = preCube[FRONT][2][1]; Cube[RIGHT][2][2] = preCube[FRONT][2][2]; Cube[BACK][2][2] = preCube[RIGHT][2][2]; Cube[BACK][2][1] = preCube[RIGHT][2][1]; Cube[BACK][2][0] = preCube[RIGHT][2][0]; Cube[LEFT][2][2] = preCube[BACK][2][2]; Cube[LEFT][2][1] = preCube[BACK][2][1]; Cube[LEFT][2][0] = preCube[BACK][2][0]; } else { Cube[FRONT][2][0] = preCube[RIGHT][2][0]; Cube[FRONT][2][1] = preCube[RIGHT][2][1]; Cube[FRONT][2][2] = preCube[RIGHT][2][2]; Cube[RIGHT][2][0] = preCube[BACK][2][0]; Cube[RIGHT][2][1] = preCube[BACK][2][1]; Cube[RIGHT][2][2] = preCube[BACK][2][2]; Cube[BACK][2][2] = preCube[LEFT][2][2]; Cube[BACK][2][1] = preCube[LEFT][2][1]; Cube[BACK][2][0] = preCube[LEFT][2][0]; Cube[LEFT][2][2] = preCube[FRONT][2][2]; Cube[LEFT][2][1] = preCube[FRONT][2][1]; Cube[LEFT][2][0] = preCube[FRONT][2][0]; } break; case LEFT: if (clockwise) { Cube[UP][0][0] = preCube[BACK][2][2]; Cube[UP][1][0] = preCube[BACK][1][2]; Cube[UP][2][0] = preCube[BACK][0][2]; Cube[FRONT][0][0] = preCube[UP][0][0]; Cube[FRONT][1][0] = preCube[UP][1][0]; Cube[FRONT][2][0] = preCube[UP][2][0]; Cube[DOWN][2][0] = preCube[FRONT][2][0]; Cube[DOWN][1][0] = preCube[FRONT][1][0]; Cube[DOWN][0][0] = preCube[FRONT][0][0]; Cube[BACK][0][2] = preCube[DOWN][2][0]; Cube[BACK][1][2] = preCube[DOWN][1][0]; Cube[BACK][2][2] = preCube[DOWN][0][0]; } else { Cube[UP][0][0] = preCube[FRONT][0][0]; Cube[UP][1][0] = preCube[FRONT][1][0]; Cube[UP][2][0] = preCube[FRONT][2][0]; Cube[FRONT][0][0] = preCube[DOWN][0][0]; Cube[FRONT][1][0] = preCube[DOWN][1][0]; Cube[FRONT][2][0] = preCube[DOWN][2][0]; Cube[DOWN][2][0] = preCube[BACK][0][2]; Cube[DOWN][1][0] = preCube[BACK][1][2]; Cube[DOWN][0][0] = preCube[BACK][2][2]; Cube[BACK][0][2] = preCube[UP][2][0]; Cube[BACK][1][2] = preCube[UP][1][0]; Cube[BACK][2][2] = preCube[UP][0][0]; } break; case RIGHT: if (clockwise) { Cube[UP][2][2] = preCube[FRONT][2][2]; Cube[UP][1][2] = preCube[FRONT][1][2]; Cube[UP][0][2] = preCube[FRONT][0][2]; Cube[BACK][0][0] = preCube[UP][2][2]; Cube[BACK][1][0] = preCube[UP][1][2]; Cube[BACK][2][0] = preCube[UP][0][2]; Cube[DOWN][0][2] = preCube[BACK][2][0]; Cube[DOWN][1][2] = preCube[BACK][1][0]; Cube[DOWN][2][2] = preCube[BACK][0][0]; Cube[FRONT][0][2] = preCube[DOWN][0][2]; Cube[FRONT][1][2] = preCube[DOWN][1][2]; Cube[FRONT][2][2] = preCube[DOWN][2][2]; } else { Cube[UP][2][2] = preCube[BACK][0][0]; Cube[UP][1][2] = preCube[BACK][1][0]; Cube[UP][0][2] = preCube[BACK][2][0]; Cube[BACK][0][0] = preCube[DOWN][2][2]; Cube[BACK][1][0] = preCube[DOWN][1][2]; Cube[BACK][2][0] = preCube[DOWN][0][2]; Cube[DOWN][0][2] = preCube[FRONT][0][2]; Cube[DOWN][1][2] = preCube[FRONT][1][2]; Cube[DOWN][2][2] = preCube[FRONT][2][2]; Cube[FRONT][0][2] = preCube[UP][0][2]; Cube[FRONT][1][2] = preCube[UP][1][2]; Cube[FRONT][2][2] = preCube[UP][2][2]; } break; } } int str_cmp(char *a, const char *b) { int pos = 0; while (a[pos] != 0 && b[pos] != 0) { if (a[pos] != b[pos]) return a[pos] - b[pos]; ++pos; } return 0; } void str_cpy(char *a, const char *b) { int pos = 0; while (b[pos] != 0) a[pos] = b[pos++]; a[pos] = 0; } typedef struct { char key[MAX_KEY + 1]; int data; } Hash; Hash tb[MAX_TABLE]; unsigned long hash(const char *str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = (((hash << 5) + hash) + c) % MAX_TABLE; } return hash % MAX_TABLE; } int find(const char *key) { unsigned long h = hash(key); int cnt = MAX_TABLE; int step = 1; while (tb[h].key[0] != 0 && cnt--) { if (str_cmp(tb[h].key, key) == 0) { return tb[h].data; } h = (h + 1) % MAX_TABLE; } return -1; } int add(const char *key, int data) { unsigned long h = hash(key); int step = 1; int i = 0; while (tb[h].key[0] != 0) { if (str_cmp(tb[h].key, key) == 0) { if (tb[h].data > data) { tb[h].data = data; } return 0; } h = (h + 1) % MAX_TABLE; } str_cpy(tb[h].key, key); tb[h].data = data; return 1; } bool isInit = false; int frontPath, rearPath; int tempCube[6][CUBE_SIZE][CUBE_SIZE]; void recursionToSetHash(int depth, int path, int idx) { char key[55] = { 0 }; int hashLen = 0; for (int i = 0; i < 6; ++i) for (int j = 0; j < CUBE_SIZE; ++j) for (int k = 0; k < CUBE_SIZE; ++k) key[hashLen++] = tempCube[i][j][k] + '0'; add(key, path); if (depth == 0) return; else { for (int i = 0; i < 6; i++) { rotateForSolve(tempCube, i, false); recursionToSetHash(depth - 1, path + ((i + 1) * 2) * idx, idx * 14); rotateForSolve(tempCube, i, true); rotateForSolve(tempCube, i, true); recursionToSetHash(depth - 1, path + ((i + 1) * 2 + 1) * idx, idx * 14); rotateForSolve(tempCube, i, false); } } } void initHash() { for (int i = 0; i < 6; ++i) for (int j = 0; j < CUBE_SIZE; ++j) for (int k = 0; k < CUBE_SIZE; ++k) tempCube[i][j][k] = i; recursionToSetHash(5, 0, 1); } void recursionToSolve(int depth, int path, int idx) { char key[55] = { 0 }; int hashLen = 0; int srcCube[6][CUBE_SIZE][CUBE_SIZE]; if (frontPath + rearPath < path) return; for (int i = 0; i < 6; ++i) for (int j = 0; j < CUBE_SIZE; ++j) for (int k = 0; k < CUBE_SIZE; ++k) key[hashLen++] = tempCube[i][j][k] + '0'; int hashData = find(key); if (hashData != -1) { if (frontPath + rearPath > hashData + path) { frontPath = hashData; rearPath = path; } } if (depth == 0) return; else { for (int i = 0; i < 6; ++i) { rotateForSolve(tempCube, i, false); recursionToSolve(depth - 1, path + ((i + 1) * 2) * idx, idx * 14); rotateForSolve(tempCube, i, true); rotateForSolve(tempCube, i, true); recursionToSolve(depth - 1, path + ((i + 1) * 2 + 1) * idx, idx * 14); rotateForSolve(tempCube, i, false); } } } void runtest(int cube[6][CUBE_SIZE][CUBE_SIZE]) { if (!isInit) { initHash(); isInit = true; } for (int i = 0; i < 6; ++i) for (int j = 0; j < CUBE_SIZE; ++j) for (int k = 0; k < CUBE_SIZE; ++k) tempCube[i][j][k] = cube[i][j][k]; frontPath = rearPath = 100000000; recursionToSolve(5, 0, 1); for (int i = 0; i < 5; ++i) { if (rearPath % 14 / 2 > 0) { rotate(rearPath % 14 / 2 - 1, rearPath % 14 % 2 == 1); } rearPath /= 14; } for (int i = 14 * 14 * 14 * 14; i > 0; i /= 14) { if (frontPath / i / 2 > 0) { rotate(frontPath / i / 2 - 1, !(frontPath / i % 2 == 1)); } frontPath %= i; } }