Cubes
In a 3×3×1 box (width×length×height) placed horizontally on a table, there are eight 1×1×1 cubes arranged in a single layer, with their faces parallel to the box's faces. Each cube has 5 white faces and 1 red face.
You can make a move by rolling any cube adjacent to the free space into that space, over its edge. The goal is to reach a final position where the free space is at the center of the box, and all cubes have their red faces facing upwards towards the observer (assuming you are viewing the box from above). Your task is to find the minimum number of moves needed to achieve this final configuration from the initial setup.
Input
The input consists of 3 rows, each containing 3 characters. Each character represents the position of the red face of a cube or the free space in the initial configuration:
. - free space
+ - red face facing the observer
* - red face facing away from the observer (towards the bottom of the box)
U - red face on top
D - red face on the bottom
L - red face on the left
R - red face on the right
Output
The output should be a single integer representing the minimum number of moves required. If it's impossible to achieve the desired configuration, output -1.