prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem F:</font> Traveling Cube</H1>3 4<p>5On a small planet named Bandai, a landing party of the starship Tadamigawa discovered colorful6cubes traveling on flat areas of the planet surface, which the landing party named beds. A cube7appears at a certain position on a bed, travels on the bed for a while, and then disappears. After8a longtime observation, a science officer Lt. Alyssa Ogawa of Tadamigawa found the rule how a9cube travels on a bed.10</p>11<p>12A bed is a rectangular area tiled with squares of the same size.13 14</p>15 16<ul>17<li> One of the squares is colored red,</li>18<li>  one colored green,</li>19<li>  one colored blue,</li>20<li>  one colored cyan,</li>21<li>  one colored magenta,</li>22<li>  one colored yellow,</li>23<li>  one or more colored white, and</li>24<li>  all others, if any, colored black.</li>25</ul>26 27<p>28Initially, a cube appears on one of the white squares. The cube’s faces are colored as follows.29</p>30<pre>31             top  red32          bottom  cyan33           north  green34           south  magenta35            east  blue36            west  yellow37</pre>38<p>39The cube can roll around a side of the current square at a step and thus rolls on to an adjacent40square. When the cube rolls on to a chromatically colored (red, green, blue, cyan, magenta or41yellow) square, the top face of the cube after the roll should be colored the same. When the42cube rolls on to a white square, there is no such restriction. The cube should never roll on to a43black square.44</p>45 46<p>47Throughout the travel, the cube can visit each of the chromatically colored squares only once,48and any of the white squares arbitrarily many times. As already mentioned, the cube can never49visit any of the black squares. On visit to the final chromatically colored square, the cube50disappears. Somehow the order of visits to the chromatically colored squares is known to us51before the travel starts.52</p>53<p>54Your mission is to find the least number of steps for the cube to visit all the chromatically55colored squares in the given order.56 57</p>58 59<H2>Input</H2>60 61<p>62The input is a sequence of datasets. A dataset is formatted as follows:63</p>64<pre>65      <i>w d</i><br>66      <i>c</i><sub>11</sub> . . . <i>c</i><sub><i>w</i>1</sub>67       .        .68       .        .69       .        .70      <i>c</i><sub>1<i>d</i></sub> . . . <i>c</i><sub><i>wd</i></sub>71      <i>v</i><sub>1</sub><i>v</i><sub>2</sub><i>v</i><sub>3</sub><i>v</i><sub>4</sub><i>v</i><sub>5</sub><i>v</i><sub>6</sub>72</pre>73 74<p>75The first line is a pair of positive integers w and d separated by a space. The next d lines are76w-character-long strings <i>c</i><sub>11</sub> . . . <i>c</i><sub><i>w</i>1</sub> , . . . , <i>c</i><sub>1<i>d</i></sub> . . . <i>c<sub>wd</sub></i> with no spaces. Each character cij is one of77the letters r, g, b, c, m, y, w and k, which stands for red, green, blue, cyan, magenta, yellow,78white and black respectively, or a sign #. Each of r, g, b, c, m, y and # occurs once and only once79in a dataset. The last line is a six-character-long string  <i>v</i><sub>1</sub><i>v</i><sub>2</sub><i>v</i><sub>3</sub><i>v</i><sub>4</sub><i>v</i><sub>5</sub><i>v</i><sub>6</sub> which is a permutation of80“rgbcmy”.81</p>82<p>83The integers <i>w</i> and <i>d</i> denote the width (the length from the east end to the west end) and the84depth (the length from the north end to the south end) of a bed. The unit is the length of a85side of a square. You can assume that neither <i>w</i> nor d is greater than 30.86</p>87<p>88Each character <i>c<sub>ij</sub></i> shows the color of a square in the bed. The characters <i>c</i><sub>11</sub> , <i>c</i><sub><i>w</i>1</sub> , <i>c</i><sub>1<i>d</i></sub> and <i>c<sub>wd</sub></i>89correspond to the north-west corner, the north-east corner, the south-west corner and the south-90east corner of the bed respectively. If <i>c<sub>ij</sub></i> is a letter, it indicates the color of the corresponding91square. If <i>c<sub>ij</sub></i> is a #, the corresponding square is colored white and is the initial position of the92cube.93</p>94<p>95The string <i>v</i><sub>1</sub><i>v</i><sub>2</sub><i>v</i><sub>3</sub><i>v</i><sub>4</sub><i>v</i><sub>5</sub><i>v</i><sub>6</sub> shows the order of colors of squares to visit. The cube should visit the96squares colored <i>v</i><sub>1</sub>, <i>v</i><sub>2</sub> , <i>v</i><sub>3</sub> , <i>v</i><sub>4</sub> , <i>v</i><sub>5</sub> and <i>v</i><sub>6</sub> in this order.97</p>98<p>99The end of the input is indicated by a line containing two zeros separated by a space.100 101</p>102 103<H2>Output</H2>104 105<p>106For each input dataset, output the least number of steps if there is a solution, or "unreachable"107if there is no solution. In either case, print it in one line for each input dataset.108 109</p>110 111<H2>Sample Input</H2>112<pre>11310 5114kkkkkwwwww115w#wwwrwwww116wwwwbgwwww117kwwmcwwwkk118kkwywwwkkk119rgbcmy12010 5121kkkkkkkkkk122k#kkkkkkkk123kwkkkkkwwk124kcmyrgbwwk125kwwwwwwwwk126cmyrgb12710 5128kkkkkkkkkk129k#kkkkkkkk130kwkkkkkwkk131kcmyrgbwwk132kwwwwwwwwk133cmyrgb1340 0135 136</pre>137 138<H2>Output for the Sample Input</H2>139<pre>140914149142unreachable143</pre>144 145 146