Dice Room

Time limit8sMemory limit512 MB

Summary

Given hole patterns on the six faces of a cube, find the fewest 90-degree rolls so that holes exist at the right positions on the front and back faces.

Level: Hard8 of 10
Topics: BFS, Simulation, Implementation
Solved: No attempts yet

Problem

You are playing a game known for its deep story and its puzzles. Your character is locked alone in a strange house with no way to call for help, so you have to escape on your own. Almost every room in the house holds a puzzle, and you cannot move to the next room until you solve it.

In one room a device shaped like a die sits on a table in the center, and the wall carries this notice.

This cube is a remote controller. You use it to operate a distant room called the Dice Room. That room is also a cube, and each of its six sides is made up of 3x3 unit squares. Some of those squares have a hole large enough for a person to pass through. You can roll the controller only so that at least one edge always touches the table while it turns, that is, in four directions. Rolling the controller rolls the Dice Room the same way and moves the holes with it. To get through the room, at least one of the lower three squares on the front side and at least one of the lower three squares on the back side must have a hole.

The Dice Room

Figure 1: the Dice Room. The shaded band covers the lower three squares of the front side and of the back side.

The four available rotations

Figure 2: the available rotations. One rotation rolls the cube 90 degrees forward, backward, to the left, or to the right. Spinning it in place around the vertical axis is not allowed.

A monitor shows where the holes are right now. Before you travel to the Dice Room you have to roll the controller until the room can be crossed. Rolling the room takes time and you do not have much of it, so you want as few rotations as possible. How many rotations do you need to make the Dice Room passable?

Input

The input holds several datasets. One dataset is 6 tables of 3x3 characters, and each table gives the starting position of the holes on one side of the room. Each character is * or ., and * marks a hole. The six sides come in this order: front, right, back, left, top, bottom.

The orientation of each table follows the development view below. Side 1 is the front, 2 is the right, 3 is the back, 4 is the left, 5 is the top, and 6 is the bottom. Sides 1, 2, 3 and 4 run left to right in that order, side 5 is attached above side 1, and side 6 is attached below side 1. When the view is folded up, the bottom printed row of sides 1, 2, 3 and 4 becomes the bottom row of the room, the bottom printed row of side 5 meets the front side, and the top printed row of side 6 meets the front side.

Development view

Figure 3: the development view. The shaded band marks the lower three squares of the front side and of the back side.

A blank line follows each dataset. The end of the input is a single line holding #.

Output

For each dataset, print the minimum number of rotations on its own line. Every dataset has an answer.

Examples5

Example 1

Input

...
...
.*.
...
...
.*.
...
...
...
...
...
.*.
...
...
.*.
...
...
...

...
.*.
...
*..
...
..*
*.*
*.*
*.*
*.*
.*.
*.*
*..
.*.
..*
*.*
...
*.*

...
.*.
.*.
...
.**
*..
...
...
.*.
.*.
...
*..
..*
...
.**
...
*..
...

#

Expected output

3
1
0

Example 2

Input

...
...
.*.
...
...
...
...
...
.*.
...
...
...
...
...
...
...
...
...

#

Expected output

Example 3

Input

...
...
*..
...
...
...
...
...
..*
...
...
...
...
...
...
...
...
...

#

Expected output

Example 4

Input

***
***
***
***
***
***
***
***
***
***
***
***
***
***
***
***
***
***

#

Expected output

Example 5

Input

...
...
...
...
...
...
...
...
...
...
...
...
...
...
*..
..*
...
...

..*
...
...
...
...
...
..*
...
...
...
...
...
...
...
...
...
...
...

...
...
...
..*
...
...
...
...
...
..*
...
...
...
...
...
...
...
...

#

Expected output

1
2
3