Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: The Morning after Halloween
Description You are working for an amusement park as an operator of an In this problem, you are asked to write a program that, given a floor map of a house, finds the smallest number of steps to move all ghosts to the positions where they are supposed to be. A floor consists of a matrix of square cells. A cell is either a wall cell where ghosts cannot move into or a corridor cell where they can. At each step, you can move any number of ghosts simultaneously. Every ghost can either stay in the current cell, or move to one of the corridor cells in its 4-neighborhood (i.e. immediately left, right, up or down), if the ghosts satisfy the following conditions: No more than one ghost occupies one position at the end of the step. No pair of ghosts exchange their positions one another in the step.
For example, suppose ghosts are located as shown in the following (partial) map, where a sharp sign (‘ #### The following four maps show the only possible positions of the ghosts after one step.
Input The 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.
4 ≤ Subsequent a ‘ `#`’ representing a wall cell,a lowercase letter representing a corridor cell which is the initial position of a ghost, an uppercase letter representing a corridor cell which is the position where the ghost corresponding to its lowercase letter is supposed to be, or a space representing a corridor cell that is none of the above.
In each map, each of the first The last dataset is followed by a line containing three zeros separated by a space. Output For each dataset in the input, one line containing the smallest number of steps to restore ghosts into the positions where they are supposed to be should be output. An output line should not contain extra characters such as spaces. Sample Input 5 5 2 ##### #A#B# # # #b#a# ##### 16 4 3 ################ ## ########## ## # ABCcba # ################ 16 16 3 ################ ### ## # ## ## # ## # c# # ## ########b# # ## # # # # # # ## # # ## ## a# # # # # ### ## #### ## # ## # # # # # ##### # ## ## #### #B# # # ## C# # ### # # # ####### # # ###### A## # # # ## ################ 0 0 0 Sample Output 7 36 77 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator