Description

You are asked to write a program that, on a map, finds the minimum number of steps to move each ghost to its designated position. The map consists of small cells. Each cell is either a wall (ghosts cannot enter) or a corridor (ghosts can enter).

In each step, you may move any number of ghosts simultaneously. Each ghost either stays put or moves to an adjacent cell (adjacent cells share an edge). A move is valid if it satisfies all of the following:

1. No more than one ghost occupies the same cell.
2. No pair of ghosts swaps positions in a single step.

For example, suppose the ghosts are placed as shown in the figure to the right. Here, # denotes a wall, a space denotes a corridor, and a, b, c denote ghosts:

####
 ab#
#c##
####

After one step, the map can become any of the following:

####     ####     ####       ####
 ab#     a b#     acb#       ab #
#c##     #c##     # ##       #c##   
####     ####     ####       ####

Input Format

The input contains at most $10$ test cases. Each test case describes one map in the following format:

$$\begin{matrix} w & h & n \\ c_{1,1} & c_{1,2} & \cdots & c_{1,w} \\ c_{2,1} & c_{2,2} & \cdots & c_{2,w} \\ \vdots & \vdots & \ddots & \vdots \\ c_{h,1} & c_{h,2} & \cdots & c_{h,w} \\ \end{matrix}$$

The first line contains $w, h$ and $n$, where $w$ and $h$ are the width and height of the map, and $n$ is the number of ghosts. They satisfy $4 \le w \le 16$, $4 \le h \le 16$, $1 \le n \le 3$.

The next $h$ lines each contain $w$ characters:

• # denotes a wall.
• A lowercase letter denotes a ghost’s initial position (which is also a corridor).
• An uppercase letter denotes a ghost’s target position (which is also a corridor).
• A space denotes an empty corridor.

In each map, the first $n$ lowercase letters and the first $n$ uppercase letters denote the ghosts’ initial positions and their target positions, respectively. The outer boundary of the map is walled: every character in the first and last rows is #, and the first and last character of every row is also #. All corridor cells are connected; likewise, all wall cells are connected. In every $2 \times 2$ area on the map, at least one cell is a wall (#). We need to move each ghost denoted by a lowercase letter to the corresponding uppercase letter’s position.

A line containing three zeros $0$ $0$ $0$ follows the last test case.

Output Format

For each test case, output a single integer on one line: the minimum number of moves.

5 5 2
#####
#A#B#
#   #
#b#a#
#####
16 4 3
################
## ########## ##
#    ABCcba    #
################
16 16 3
################
### ##    #   ##
##  #  ##   # c#
#  ## ########b#
# ##  # #   #  #
#  # ##   # # ##
##  a#  # # #  #
### ## #### ## #
##   #   #  #  #
#  ##### # ## ##
####   #B# #   #
##  C#   #   ###
#  # # ####### #
# ######  A##  #
#        #     #
################
0 0 0

7
36
77

Hint

Translated by ChatGPT 5