{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003cfont color\u003d\"#000\"\u003eProblem G:\u003c/font\u003e \u003c/h1\u003e\n\n\u003cp\u003e\nYou are working for an amusement park as an operator of an \u003ci\u003eobakeyashiki\u003c/i\u003e, or a haunted house,\nin which guests walk through narrow and dark corridors. The house is proud of their lively\nghosts, which are actually robots remotely controlled by the operator, hiding here and there in\nthe corridors. One morning, you found that the ghosts are not in the positions where they are\nsupposed to be. Ah, yesterday was Halloween. Believe or not, paranormal spirits have moved\nthem around the corridors in the night. You have to move them into their right positions before\nguests come. Your manager is eager to know how long it takes to restore the ghosts.\n\u003c/p\u003e\n\n\u003cp\u003e\nIn this problem, you are asked to write a program that, given a floor map of a house, finds the\nsmallest number of steps to move all ghosts to the positions where they are supposed to be.\n\u003c/p\u003e\n\n\u003cp\u003e\nA floor consists of a matrix of square cells. A cell is either a wall cell where ghosts cannot move\ninto or a corridor cell where they can.\n\u003c/p\u003e\n\n\u003cp\u003e\nAt each step, you can move any number of ghosts simultaneously. Every ghost can either stay\nin the current cell, or move to one of the corridor cells in its 4-neighborhood (i.e. immediately\nleft, right, up or down), if the ghosts satisfy the following conditions:\n\u003c/p\u003e\n\n\u003col\u003e\n\u003cli\u003e No more than one ghost occupies one position at the end of the step.\u003c/li\u003e\n\u003cli\u003e No pair of ghosts exchange their positions one another in the step.\u003c/li\u003e\n\u003c/ol\u003e\n\n\n\u003cp\u003e\nFor example, suppose ghosts are located as shown in the following (partial) map, where a sharp sign (\u0027\u003cspan\u003e#\u003c/span\u003e) represents a wall cell and \u0027a\u0027, \u0027b\u0027, and \u0027c\u0027 ghosts.\n\u003c/p\u003e\n\u003cpre\u003e ####\n ab#\n #c##\n ####\n\u003c/pre\u003e\n\n\u003cp\u003e\nThe following four maps show the only possible positions of the ghosts after one step.\n\u003c/p\u003e\n\n\u003cpre\u003e #### #### #### ####\n ab# a b# acb# ab #\n #c## #c## # ## #c##\n #### #### #### ####\n\u003c/pre\u003e\n\n\n\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe 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.\n\u003c/p\u003e\n\n\u003cpre\u003e\u003ci\u003ew h n\u003c/i\u003e\n\u003ci\u003ec\u003c/i\u003e\u003csub\u003e11\u003c/sub\u003e\u003ci\u003ec\u003c/i\u003e\u003csub\u003e12\u003c/sub\u003e...\u003ci\u003ec\u003c/i\u003e\u003csub\u003e1\u003ci\u003ew\u003c/i\u003e\u003c/sub\u003e\n\u003ci\u003ec\u003c/i\u003e\u003csub\u003e21\u003c/sub\u003e\u003ci\u003ec\u003c/i\u003e\u003csub\u003e22\u003c/sub\u003e...\u003ci\u003ec\u003c/i\u003e\u003csub\u003e2\u003ci\u003ew\u003c/i\u003e\u003c/sub\u003e\n. . .. .\n.. .\n .\n.. .\n\u003ci\u003ec\u003c/i\u003e\u003csub\u003e\u003ci\u003eh\u003c/i\u003e1\u003c/sub\u003e\u003ci\u003ec\u003c/i\u003e\u003csub\u003e\u003ci\u003eh\u003c/i\u003e2\u003c/sub\u003e...\u003ci\u003ec\u003c/i\u003e\u003csub\u003e\u003ci\u003eh\u003c/i\u003e\u003ci\u003ew\u003c/i\u003e\u003c/sub\u003e\n\u003c/pre\u003e\n\n\u003cp\u003e\n\u003ci\u003ew\u003c/i\u003e, \u003ci\u003eh\u003c/i\u003e and \u003ci\u003en\u003c/i\u003e in the first line are integers, separated by a space. \u003ci\u003ew\u003c/i\u003e and \u003ci\u003eh\u003c/i\u003e are the floor width\nand height of the house, respectively. \u003ci\u003en\u003c/i\u003e is the number of ghosts. They satisfy the following constraints.\n\u003c/p\u003e\n\u003ccenter\u003e\n\u003cp\u003e\n 4 ≤ \u003ci\u003ew\u003c/i\u003e ≤ 16\n\u003c/p\u003e\n\u003cp\u003e\n 4 ≤ \u003ci\u003eh\u003c/i\u003e ≤ 16\n\u003c/p\u003e\n\u003cp\u003e\n 1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 3\n\u003c/p\u003e\n\u003c/center\u003e\n\n\u003cp\u003e\nSubsequent \u003ci\u003eh\u003c/i\u003e lines of \u003ci\u003ew\u003c/i\u003e characters are the floor map. Each of \u003ci\u003ec\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e is either:\n\u003c/p\u003e\n\n\u003cul\u003e\n \u003cli\u003ea \u0027\u003cspan\u003e#\u003c/span\u003e\u0027 representing a wall cell,\u003c/li\u003e\n \u003cli\u003e a lowercase letter representing a corridor cell which is the initial position of a ghost,\u003c/li\u003e\n \u003cli\u003e an uppercase letter representing a corridor cell which is the position where the ghost corresponding to its lowercase letter is supposed to be, or\u003c/li\u003e\n \u003cli\u003e a space representing a corridor cell that is none of the above.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nIn each map, each of the first \u003ci\u003en\u003c/i\u003e letters from a and the first n letters from A appears once and\nonly once. Outermost cells of a map are walls; i.e. all characters of the first and last lines are\nsharps; and the first and last characters on each line are also sharps. All corridor cells in a\nmap are connected; i.e. given a corridor cell, you can reach any other corridor cell by following\ncorridor cells in the 4-neighborhoods. Similarly, all wall cells are connected. Any 2 × 2 area on\nany 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.\n\u003c/p\u003e\n\u003cp\u003e\nThe last dataset is followed by a line containing three zeros separated by a space.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nFor each dataset in the input, one line containing the smallest number of steps to restore ghosts\ninto the positions where they are supposed to be should be output. An output line should not\ncontain extra characters such as spaces.\n\n\u003c/p\u003e\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 5 2\n#####\n#A#B#\n# #\n#b#a#\n#####\n16 4 3\n################\n## ########## ##\n# ABCcba #\n################\n16 16 3\n################\n### ## # ##\n## # ## # c#\n# ## ########b#\n# ## # # # #\n# # ## # # ##\n## a# # # # #\n### ## #### ## #\n## # # # #\n# ##### # ## ##\n#### #B# # #\n## C# # ###\n# # # ####### #\n# ###### A## #\n# # ##\n################\n0 0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n36\n77\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\n\n\n"}}]}