prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem C:</font> Cubic Eight-Puzzle</H1>3 4<p>5Let's play a puzzle using eight cubes placed on a 3 &times; 3 board leaving one empty square.6</p>7<p>8Faces of cubes are painted with three colors. As a puzzle step, you can roll one of the cubes to9the adjacent empty square. Your goal is to make the specified color pattern visible from above10by a number of such steps.11</p>12<p>13The rules of this puzzle are as follows.14</p>15 16<ol>17<li>18<b>Coloring of Cubes:</b> All the cubes are colored in the same way as shown in Figure 3.19The opposite faces have the same color.20 21<br><br>22<center>23<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_cubic8Puzzle1">24<p>Figure 3: Coloring of a cube</p>25</center>26<br>27 28</li>29 30<li>31<b>Initial Board State:</b> Eight cubes are placed on the 3 &times; 3 board leaving one empty square.32All the cubes have the same orientation as shown in Figure 4. As shown in the figure,33squares on the board are given <i>x</i> and <i>y</i> coordinates, (1, 1), (1, 2), .. ., and (3, 3). The34position of the initially empty square may vary.35 36<br><br>37<center>38<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_cubic8Puzzle2">39<p>Figure 4: Initial board state</p>40</center>41<br>42</li>43 44 45<li>46<b>Rolling Cubes:</b> At each step, we can choose one of the cubes adjacent to the empty square and roll it into the empty square, leaving the original position empty. Figure 547shows an example.48 49<br><br>50<center>51<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_cubic8Puzzle3">52<p>Figure 5: Rolling a cube</p>53</center>54<br>55</li>56 57<li>58<b>Goal:</b> The goal of this puzzle is to arrange the cubes so that their top faces form the59specified color pattern by a number of cube rolling steps described above.60 61</li>62 63</ol>64 65 66<p>67Your task is to write a program that finds the minimum number of steps required to make the68specified color pattern from the given initial state.69</p>70 71 72 73<H2>Input</H2>74 75<p>76The input is a sequence of datasets. The end of the input is indicated by a line containing two77zeros separated by a space. The number of datasets is less than 16. Each dataset is formatted78as follows.79</p>80<pre>81        <i>x y</i>82        <i>F</i><sub>11</sub> <i>F</i><sub>21</sub> <i>F</i><sub>31</sub>83        <i>F</i><sub>12</sub> <i>F</i><sub>22</sub> <i>F</i><sub>32</sub>84        <i>F</i><sub>13</sub> <i>F</i><sub>23</sub> <i>F</i><sub>33</sub>85</pre>86 87<p>    88The first line contains two integers <i>x</i> and <i>y</i> separated by a space, indicating the position (<i>x</i>, <i>y</i>)89of the initially empty square. The values of <i>x</i> and <i>y</i> are 1, 2, or 3.90</p>91<p>92The following three lines specify the color pattern to make. Each line contains three characters93<i>F</i><sub>1<i>j</i></sub>, <i>F</i><sub>2<i>j</i></sub>, and <i>F</i><sub>3<i>j</i></sub>, separated by a space. Character <i>F<sub>ij</sub></i> indicates the top color of the cube, if any, at position (<i>i</i>, <i>j</i>) as follows:94</p>95<pre>96       B: Blue97       W: White98       R: Red99       E: the square is Empty.100</pre>101 102<p>103There is exactly one '<span>E</span>' character in each dataset.104 105</p>106 107<H2>Output</H2>108 109<p>110For each dataset, output the minimum number of steps to achieve the goal, when the goal can111be reached within 30 steps. Otherwise, output "<span>-1</span>" for the dataset.112</p>113 114<H2>Sample Input</H2>115<pre>1161 2117W W W118E W W119W W W1202 1121R B W122R W W123E W W1243 3125W B W126B R E127R B R1283 3129B W R130B W R131B E R1322 1133B B B134B R B135B R E1361 1137R R R138W W W139R R E1402 1141R R R142B W B143R R E1443 2145R R R146W E W147R R R1480 0149</pre>150 151<H2>Output for the Sample Input</H2>152<pre>1530154315513156231572915830159-1160-1161</pre>162 163 164 165 166