Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
72 - ZOJ Monthly, November 2008 - D
Die Board Game

Time Limit: 5 Seconds      Memory Limit: 32768 KB

The die board game is played on a board divided into N * M squares. The rows of the board are numbered from 0 to N-1 from north to south and the columns are numbered from 0 to M-1 from west to east. See the figure below for more details of the direction. Each square is identified by a pair (x, y) where x is a row number and y is a column number.

A die is a cube whose six faces are labeled with 1, 2, 3, 4, 5, and 6 dots, respectively. Each of the faces 1, 2, and 3 is adjacent to the other two. If the die is viewed so that faces 1, 2, and 3 are visible, face 1 is on top, and face 2 is in front, then face 3 will be seen on the right side of the die, as in the figure below. Faces 4, 5, and 6 are opposite to faces 3, 2, and 1, respectively.

The game begins with a die placed on a square. To move the die the player must roll the die over an edge to an adjacent (either horizontally or vertically) square. The goal of the game is to roll the die from the starting square to the target square so that the number of moves is minimal. What's more, the die must start and end with given states.

Input

The input consists of several test cases. There is an empty line between cases.

For each case, the first line contains two integers N and M (1 <= N, M <= 100). The following N lines each contains M characters of '#' or '.', where '#' for an obtacle and '.' for an empty square. The player can not roll the die to a square occupied by an obstacle. The next line contains four integers x1, y1, x2, y2 separated by single space. (x1, y1) and (x2, y2) are the starting and target square respectively. You can assume they are empty. Last two lines are the description of the die at the starting and target square respectively. Each line contains six faces of a die, by the order top, bottom, north, south, west, east. The first sample corresponds to the game shown in the figure above, and the five steps are (0,0)->(0,1)->(1,1)->(2,1)->(3,1)->(3,2).

Output

If the die can be rolled from the starting square to the target square with the right states, output the minimum number of steps it takes. Otherwise, just output -1.

Sample Input

4 3
..#
...
...
...
0 0 3 2
1 6 5 2 4 3
6 1 4 3 5 2

1 3
.#.
0 0 0 2
1 6 5 2 4 3
6 1 5 2 3 4

Sample Output

5
-1

Author: GAO, Yuan
Submit    Status