673 . Traveling Cube
Description
On a small planet named Bandai, a landing party of the starship Tadamigawa discovered colorful cubes traveling on flat areas of the planet surface, which the landing party named beds. A cube appears at a certain position on a bed, travels on the bed for a while, and then disappears. After a longtime observation, a science officer Lt. Alyssa Ogawa of Tadamigawa found the rule how a cube travels on a bed. A bed is a rectangular area tiled with squares of the same size. • One of the squares is colored red, • one colored green, • one colored blue, • one colored cyan, • one colored magenta, • one colored yellow, • one or more colored white, and • all others, if any, colored black. Initially, a cube appears on one of the white squares. The cube’s faces are colored as follows.The cube can roll around a side of the current square at a step and thus rolls on to an adjacent square. When the cube rolls on to a chromatically colored (red, green, blue, cyan, magenta or yellow) square, the top face of the cube after the roll should be colored the same. When the cube rolls on to a white square, there is no such restriction. The cube should never roll on to a black square. Throughout the travel, the cube can visit each of the chromatically colored squares only once, and any of the white squares arbitrarily many times. As already mentioned, the cube can never visit any of the black squares. On visit to the final chromatically colored square, the cube disappears. Somehow the order of visits to the chromatically colored squares is known to us before the travel starts. Your mission is to find the least number of steps for the cube to visit all the chromatically colored squares in the given order.
Input Format
The input is a sequence of datasets. A dataset is formatted as follows:
|
w d
| ||
|
c11
| ...
| cw1
|
|
| |
|
c1d
| ...
| cwd
|
|
v1v2v3v4v5v6
| ||
The first line is a pair of positive integers w
$c_{11} \cdots c_{w1}, \cdots, c_{1d} \cdots c_{wd}$
-->
c11 ... cw1, ... , c1d ... cwd
$v_{1}v_{2}v_{3}v_{4}v_{5}v_{6}$
-->
v1v2v3v4v5v6
The integers w
Each character cij
#, the corresponding square is colored white and is the initial position of the cube.
The string <!-- MATH
$v_{1}v_{2}v_{3}v_{4}v_{5}v_{6}$
-->
v1v2v3v4v5v6
$v_{1}, v_{2}, v_{3}, v_{4}, v_{5}$
-->
v1, v2, v3, v4, v5
Output Format
For each input dataset, output the least number of steps if there is a solution, or ``unreachable" if there is no solution. In either case, print it in one line for each input dataset.
Sample Input 1
10 5
kkkkkwwwww
w#wwwrwwww
wwwwbgwwww
kwwmcwwwkk
kkwywwwkkk
rgbcmy
10 5
kkkkkkkkkk
k#kkkkkkkk
kwkkkkkwwk
kcmyrgbwwk
kwwwwwwwwk
cmyrgb
10 5
kkkkkkkkkk
k#kkkkkkkk
kwkkkkkwkk
kcmyrgbwwk
kwwwwwwwwk
cmyrgb
0 0
Sample Output 1
9
49
unreachable
Hints
Problem Source
Migrated from old NTUJ.
Aizu 2008
Subtasks
| No. | Testdata Range | Score |
|---|