prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem G:</font> The Morning after Halloween</H1>3 4<p>5You are working for an amusement park as an operator of an <i>obakeyashiki</i>, or a haunted house,6in which guests walk through narrow and dark corridors. The house is proud of their lively7ghosts, which are actually robots remotely controlled by the operator, hiding here and there in8the corridors. One morning, you found that the ghosts are not in the positions where they are9supposed to be. Ah, yesterday was Halloween. Believe or not, paranormal spirits have moved10them around the corridors in the night. You have to move them into their right positions before11guests come. Your manager is eager to know how long it takes to restore the ghosts.12</p>13 14<p>15In this problem, you are asked to write a program that, given a floor map of a house, finds the16smallest number of steps to move all ghosts to the positions where they are supposed to be.17</p>18 19<p>20A floor consists of a matrix of square cells. A cell is either a wall cell where ghosts cannot move21into or a corridor cell where they can.22</p>23 24<p>25At each step, you can move any number of ghosts simultaneously. Every ghost can either stay26in the current cell, or move to one of the corridor cells in its 4-neighborhood (i.e. immediately27left, right, up or down), if the ghosts satisfy the following conditions:28</p>29 30<ol>31<li> No more than one ghost occupies one position at the end of the step.</li>32<li> No pair of ghosts exchange their positions one another in the step.</li>33</ol>34 35 36<p>37For example, suppose ghosts are located as shown in the following (partial) map, where a sharp sign ('<span>#</span></i>) represents a wall cell and 'a', 'b', and 'c' ghosts.38</p>39<pre>40                                                 ####41                                                  ab#42                                                 #c##43                                                 ####44</pre>45 46<p>47The following four maps show the only possible positions of the ghosts after one step.48</p>49 50<pre>51                                   ####      ####     ####     ####52                                    ab#      a b#     acb#     ab #53                                   #c##      #c##     # ##     #c##54                                   ####      ####     ####     ####55</pre>56 57 58 59 60<H2>Input</H2>61 62<p>63The input consists of at most 10 datasets, each of which represents a floor map of a house. The format of a dataset is as follows.64</p>65 66<pre>67<i>w h n</i>68<i>c</i><sub>11</sub><i>c</i><sub>12</sub>...<i>c</i><sub>1<i>w</i></sub>69<i>c</i><sub>21</sub><i>c</i><sub>22</sub>...<i>c</i><sub>2<i>w</i></sub>70. . ..       .71..           .72          .73..           .74<i>c</i><sub><i>h</i>1</sub><i>c</i><sub><i>h</i>2</sub>...<i>c</i><sub><i>h</i><i>w</i></sub>75</pre>76 77<p>78<i>w</i>, <i>h</i> and <i>n</i> in the first line are integers, separated by a space. <i>w</i> and <i>h</i> are the floor width79and height of the house, respectively. <i>n</i> is the number of ghosts. They satisfy the following constraints.80</p>81<center>82<p>83                            4 &le; <i>w</i> &le; 1684</p>85<p>86      4 &le; <i>h</i> &le; 1687</p>88<p>89      1 &le; <i>n</i> &le; 390</p>91</center>92 93<p>94Subsequent <i>h</i> lines of <i>w</i> characters are the floor map. Each of <i>c<sub>ij</sub></i> is either:95</p>96 97<ul>98    <li>a '<span>#</span>' representing a wall cell,</li>99   <li> a lowercase letter representing a corridor cell which is the initial position of a ghost,</li>100   <li> an uppercase letter representing a corridor cell which is the position where the ghost corresponding to its lowercase letter is supposed to be, or</li>101   <li> a space representing a corridor cell that is none of the above.</li>102</ul>103 104<p>105In each map, each of the first <i>n</i> letters from a and the first n letters from A appears once and106only once. Outermost cells of a map are walls; i.e. all characters of the first and last lines are107sharps; and the first and last characters on each line are also sharps. All corridor cells in a108map are connected; i.e. given a corridor cell, you can reach any other corridor cell by following109corridor cells in the 4-neighborhoods. Similarly, all wall cells are connected. Any 2 &times; 2 area on110any map has at least one sharp. You can assume that every map has a sequence of moves of ghosts that restores all ghosts to the positions where they are supposed to be.111</p>112<p>113The last dataset is followed by a line containing three zeros separated by a space.114</p>115 116<H2>Output</H2>117 118<p>119For each dataset in the input, one line containing the smallest number of steps to restore ghosts120into the positions where they are supposed to be should be output. An output line should not121contain extra characters such as spaces.122 123</p>124 125<H2>Sample Input</H2>126<pre>1275 5 2128#####129#A#B#130#   #131#b#a#132#####13316 4 3134################135## ########## ##136#    ABCcba    #137################13816 16 3139################140### ##    #   ##141##  #  ##   # c#142#  ## ########b#143# ##  # #   #  #144#  # ##   # # ##145##  a#  # # #  #146### ## #### ## #147##   #   #  #  #148#  ##### # ## ##149####   #B# #   #150##  C#   #   ###151#  # # ####### #152# ######  A##  #153#        #    ##154################1550 0 0156</pre>157 158<H2>Output for the Sample Input</H2>159<pre>16071613616277163</pre>164 165 166 167 168