Curious Fleas

Your most prized possession is your flea circus. The main attraction of this circus is the act performed by six acrobatic fleas. One day, you accidentally knock over the container holding these fleas, and they all spill out onto the 4×4 grid of square tiles that make up your kitchen floor. Surprisingly, no two fleas land on the same tile.

Your son Andy has a (normal, six-sided) die that is exactly the same size as a grid square. You decide to play a game. First, you place the die precisely on a single tile with no fleas. Then, you start rolling the die over an edge onto one of the adjacent tiles. The fleas are very curious; they like to explore. Whenever you move the die onto a square containing a flea, it jumps to the bottom of the die. The fleas are small enough to hide in the recesses formed by the dots on the die, so they won't be killed in the process. Similarly, if a flea is on the side of the die that is moved to the floor, it jumps from the die to the tile.

The goal of your game is to move the die in such a manner that all fleas end up sitting on the die. The die cannot leave the 4×4 grid in your kitchen. An example of a solution for the first sample input follows:

Input Specification

The first line of the input indicates the number of test cases to follow. Each test case consists of a blank line followed by 4 lines of 4 characters, which describe the initial grid configuration. A “.” denotes an empty square, an “X” denotes a flea, and a “D” indicates the initial position of the die. There will always be exactly one “D” and exactly six “X” characters in each test case.

Output Specification

For each test case, output a line containing a single number: the minimum number of moves that are required to get a flea on every face of the die at the same time. If a case has no solution, output the word “impossible” instead.

Sample Input

1. 2
3. ...X
4. XXXX
5. D..X
6. ....
8. DX.X
9. .X..
10. ..X.
11. X..X

download as text file

Output for Sample Input

1. 8
2. 14

download as text file