prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem E: </font> Sliding Block Puzzle</H1>3 4<p>5In sliding block puzzles, we repeatedly slide pieces (blocks) to open spaces within a frame to establish a goal placement of pieces.6</p>7 8<p>9A puzzle creator has designed a new puzzle by combining the ideas of sliding block puzzles and mazes. The puzzle is played in a rectangular frame segmented into unit squares. Some squares are pre-occupied by obstacles. There are a number of pieces placed in the frame, one 2 &times; 2 king piece and some number of 1 &times; 1 pawn pieces. Exactly two 1 &times; 1 squares are left open. If a pawn piece is adjacent to an open square, we can slide the piece there. If a whole edge of the king piece is adjacent to two open squares, we can slide the king piece. We cannot move the obstacles. Starting from a given initial placement, the objective of the puzzle is to move the king piece to the upper-left corner of the frame. 10</p>11 12<p>13The following figure illustrates the initial placement of the fourth dataset of the sample input.14</p>15 16<center>17<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_slidingBlockPuzzle"><br/>18<p>19Figure E.1: The fourth dataset of the sample input.20</p>21</center>22 23<p>24Your task is to write a program that computes the minimum number of moves to solve the puzzle from a given placement of pieces. Here, one move means sliding either king or pawn piece to an adjacent position.25</p>26 27 28<H2>Input</H2>29 30<p>31The input is a sequence of datasets. The first line of a dataset consists of two integers <i>H</i> and <i>W</i> separated by a space, where <i>H</i> and <i>W</i> are the height and the width of the frame. The following <i>H</i> lines, each consisting of <i>W</i> characters, denote the initial placement of pieces. In those <i>H</i> lines, '<span>X</span>', '<span>o</span>', '<span>*</span>', and '<span>.</span>' denote a part of the king piece, a pawn piece, an obstacle, and an open square, respectively. There are no other characters in those <i>H</i> lines. You may assume that 3 &le; <i>H</i> &le; 50 and 3 &le; <i>W</i> &le; 50.32</p>33 34<p>35A line containing two zeros separated by a space indicates the end of the input.36</p>37 38<H2>Output</H2>39 40<p>41For each dataset, output a line containing the minimum number of moves required to move the king piece to the upper-left corner. If there is no way to do so, output <span>-1</span>.42</p>43 44<H2>Sample Input</H2>45<pre>463 347oo.48oXX49.XX503 351XXo52XX.53o.o543 555.o*XX56oooXX57oooo.587 1259oooooooooooo60ooooo*****oo61oooooo****oo62o**ooo***ooo63o***ooooo..o64o**ooooooXXo65ooooo****XXo665 3067oooooooooooooooooooooooooooooo68oooooooooooooooooooooooooooooo69o***************************oo70XX.ooooooooooooooooooooooooooo71XX.ooooooooooooooooooooooooooo720 073</pre>74 75<H2>Output for the Sample Input</H2>76<pre>771178079-18038281680782</pre>