Painted Cube

After the One Ring was found to be in Frodo's possession, Gandalf rode to seek the counsel of the head of his order, Saruman. Saruman did not share Gandalf's belief that the Ring must be destroyed, and, unwilling to let Gandalf go free to help Frodo, he locked Gandalf in the highest room of his dark tower at Isengard. To keep his prisoner occupied, the only way out of the room was a single door that could be opened solely by solving its riddle.

Searching the room, Gandalf found a peculiar lock on a door that appeared to lead to the roof of the tower. The lock was a standard six-sided cube with no markings on any of its faces. It rested on top of an $m \times n$ grid, and exactly six squares of that grid were painted.

The cube rolls one square at a time in one of four directions (up, down, left, or right). Whenever the cube rolls onto a square, only the face that lands on that square (its new bottom face) interacts with it, and the paint on that face and on the square is exchanged:

• If the landing face is blank and the square is painted, the paint moves from the square onto the face, and the square becomes blank.
• If the landing face is painted and the square is blank, the paint moves from the face onto the square, and the face becomes blank.
• If both are painted, or both are blank, nothing changes.

The door to the roof opens only if, by some sequence of rolls, the cube reaches the goal square with all six of its faces painted. Gandalf must accomplish this in the fewest possible moves.

Given the initial paint layout, the cube's starting square, and the goal square, determine the minimum number of moves needed to bring the cube to the goal square with all six of its faces painted.

For instance, for the first test case, one optimal sequence of ten moves is: down, right, right, up, right, right, down, left, right, left.

The input contains multiple test cases. Each test case is an $m \times n$ grid of characters, where $2 \le m, n \le 20$. Each character is one of:

• . — an empty square;
• P — a painted square;
• # — an illegal square that the cube may never enter;
• C — the cube's starting square;
• G — the goal square.

Every test case contains exactly six P squares, exactly one C, exactly one G, and at most twelve . squares. Consecutive test cases are separated by a single blank line. The input terminates at end of file.

For each test case, print on its own line the minimum number of moves required to reach the goal state. If the goal state cannot be reached, print -1.