Description
Doraemon enjoys solving the Rubik's Cube.
Today, he received a scrambled 2×2×2 Rubik's Cube and wants to know if he can solve it 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.
---> Please follow the link to download the code <---
Your only task is to implement solve(int n) function:
return 1 if the Rubik's Cube can be solved within n moves, otherwise return 0.
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.
You can trace the code for more detailed information.
Example I/O
| Sample Input 1 | Sample Input 2 |
 |
 |
- In sample input 1, the minimum number of moves required to solve the Rubik's Cube is 3.
Here is one way to solve it:move(DOWN); move(FRONT); move(LEFT);
Since 3 ≤ 5, output "Yes". - In sample input 2, the minimum number of moves required to solve the Rubik's Cube is 6.
Here is one way to solve it:move(UP); move(DOWN); move(RIGHT); move(BACK); move(FRONT); move(LEFT);
Since 6 > 5, output "No".
Hint
You can use recursion to implement the function and explore all possible ways to solve the Rubik's Cube.
To prevent unnecessary searches that could lead to a TLE result, make sure to terminate the function when the number of moves exceeds.
Input
- The first line contains a single integer T (1 ≤ T ≤ 10), representing the number of test cases.
- For the next T lines, each line represents a test case.
- Each test case 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 solvable.
Output
Output T lines. For each line, if the given Rubik's Cube can be solved within n moves, print "Yes", Otherwise, print "No".