14079 - Doraemon and Rubik's Cube ver.2   

Status  |  Limits Submit

Description


       
 

Doraemon enjoys solving the Rubik's Cube.
Today, he received a scrambled 2×2×2 Rubik's Cube and wants to find all the solutions that can be achieved within N moves.
Can you help him out?

To represent the state of a 2x2x2 Rubik's Cube, we use a string consisting of W, O, B, G, Y and R, representing white, orange, blue, green, yellow, and red colors, respectively, and the string has a length of 24. For more details, you can refer to the above image.

We define a move performed on a Rubik's Cube as a clockwise rotation of one of its six faces (Up, Left, Front, Right, Back, Down). To simplify this problem, the counterclockwise rotation is defined as equivalent to performing three moves.

 

Implementation

 

In this problem, the code for preprocessing the Rubik's Cube state string, I/O and some useful functions are already provided. 

#include <stdio.h>
#define UP 0
#define LEFT 1
#define FRONT 2
#define RIGHT 3
#define BACK 4
#define DOWN 5

char rubiks[6][4];
char rotateIndex[6][3][4][2] = {
    {{{0, 0}, {0, 2}, {0, 3}, {0, 1}}, {{1, 0}, {2, 0}, {3, 0}, {4, 0}}, {{1, 1}, {2, 1}, {3, 1}, {4, 1}}},
    {{{1, 0}, {1, 2}, {1, 3}, {1, 1}}, {{4, 1}, {5, 2}, {2, 2}, {0, 2}}, {{4, 3}, {5, 0}, {2, 0}, {0, 0}}},
    {{{2, 0}, {2, 2}, {2, 3}, {2, 1}}, {{1, 1}, {5, 0}, {3, 2}, {0, 3}}, {{1, 3}, {5, 1}, {3, 0}, {0, 2}}},
    {{{3, 0}, {3, 2}, {3, 3}, {3, 1}}, {{2, 1}, {5, 1}, {4, 2}, {0, 1}}, {{2, 3}, {5, 3}, {4, 0}, {0, 3}}},
    {{{4, 0}, {4, 2}, {4, 3}, {4, 1}}, {{3, 1}, {5, 3}, {1, 2}, {0, 0}}, {{3, 3}, {5, 2}, {1, 0}, {0, 1}}},
    {{{5, 0}, {5, 2}, {5, 3}, {5, 1}}, {{1, 3}, {4, 3}, {3, 3}, {2, 3}}, {{1, 2}, {4, 2}, {3, 2}, {2, 2}}}
};

int N;

void readRubiksState() {
    char state[30];
    scanf("%d %s", &N, state);
    for (int i=0; i<6; i++) {
        for (int j=0; j<4; j++) {
            rubiks[i][j] = state[i * 4 + j];
        }
    }
}

// Pass UP/LEFT/FRONT/RIGHT/BACK/DOWN as parameters to perform the move
void move(int face) {
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            int ax = rotateIndex[face][i][j][0];
            int ay = rotateIndex[face][i][j][1];
            int bx = rotateIndex[face][i][j+1][0];
            int by = rotateIndex[face][i][j+1][1];
            char tmp = rubiks[ax][ay];
            rubiks[ax][ay] = rubiks[bx][by];
            rubiks[bx][by] = tmp;
        }
    }
}

// Print the Rubik's Cube state for debugging purposes
void printRubiks() {
    printf("  %c%c\n  %c%c\n", rubiks[0][0], rubiks[0][1], rubiks[0][2], rubiks[0][3]);
    for (int i=1; i<5; i++) printf("%c%c", rubiks[i][0], rubiks[i][1]);
    printf("\n");
    for (int i=1; i<5; i++) printf("%c%c", rubiks[i][2], rubiks[i][3]);
    printf("\n  %c%c\n  %c%c\n", rubiks[5][0], rubiks[5][1], rubiks[5][2], rubiks[5][3]);
}

// Return 1 if the Rubik's Cube is solved, otherwise return 0
int isSolved() {    
    char colors[6] = {'W', 'O', 'B', 'G', 'Y', 'R'};
    int status = 0;
    for (int i=0; i<6; i++) {
        for (int j=1; j<4; j++) if (rubiks[i][0] != rubiks[i][j]) return 0;
        for (int j=0; j<6; j++) {
            if (colors[j] == rubiks[i][0]) {
                status |= (1<<j);
                break;
            }
        }
    }
    return ((1 << 6) - 1 == status);
}

// B(Back), D(Down), F(Front), L(Left), R(Right), U(Up)
char moveNotation[6] = {'U', 'L', 'F', 'R', 'B', 'D'};
int moveOrder[] = {4, 5, 2, 1, 3, 0}; 
int moveSolution[5];

// Output all the solutions that can be achieved within n moves using the terms 'B,' 'D,' 'F,' 'L,' 'R,' and 'U'
// Please keep in mind that multiple solutions may exist, so please output them in lexicographical order
void solve(int n) {
    // TODO: utilize move(), printRubiks(), isSolved() to implement the function
}

int main() {
    readRubiksState();
    solve(N);
    return 0;
}

Your only task is to implement solve(int n) function:

Output all the solutions that can be achieved within n moves using the terms 'B,' 'D,' 'F,' 'L,' 'R,' and 'U'.
Please keep in mind that multiple solutions may exist, so please output them in lexicographical order.

In your implementation, you may need to utilize the following functions:

  • move(int face): Use UP/LEFT/FRONT/RIGHT/BACK/DOWN as parameters to perform the move.
  • isSolved(): Return 1 if the Rubik's Cube is solved; otherwise, return 0.
  • printRubiks(): Print the Rubik's Cube state for debugging purposes.

There are some declared variables for your convenience:

  • moveNotation: Use these variables to output the corresponding move notations.
  • moveOrder: Sort the moves by the lexicographical order of their move notations.
  • moveSolution: You can store the solution during your recursion process.

You can trace the code for more detailed information.

 

Example I/O

 

In the sample input, there are 8 ways to solve it within 5 moves:

  • move(DOWN); move(BACK); move(DOWN);
  • move(DOWN); move(BACK); move(UP);
  • move(DOWN); move(FRONT); move(LEFT);
  • move(DOWN); move(FRONT); move(RIGHT);
  • move(UP); move(LEFT); move(BACK);
  • move(UP); move(LEFT); move(FRONT);
  • move(UP); move(RIGHT); move(DOWN);
  • move(UP); move(RIGHT); move(UP);

 

Test Case Constraints

  • 20%  n = 1
  • 80%  No further constraints

 

Input

A single line consists of an integer n (1 ≤ n ≤ 5) and a string that represents the state of a Rubik's Cube.

  • The string has a length of exactly 24 characters and contains only the characters 'Y', 'B', 'O', 'G', 'R', and 'W'.
  • It is guaranteed that the given Rubik's Cube is not in a solved state and is solvable within n moves.

 

Output

If there are x possible solutions, then please output x lines.
Each line should consist of the solution for the given Rubik's Cube using the terms 'B,' 'D,' 'F,' 'L,' 'R,' and 'U,' and ensure that they are presented in lexicographical order.

 

Sample Input  Download

Sample Output  Download

Tags




Discuss