题目描述

要求你写一个程序，在一个地图中，找到最小步数将每个鬼移动到他们指定的位置。地图包含一些小方格。每格要么是墙（鬼不能进入），要么是走廊（鬼能进入）。

每一步里，你可以同时移动任意数量的鬼。每个鬼要么待在原地不动，要么移动到相邻的格子里（相邻的格子有公共边），如果移动满足下列条件，则移动是可行的。

1. 没有一个以上的鬼在同一个格子里；
2. 没有一对鬼在一步里交换了位置。

例如，假设鬼的位置是如右上图所示的，其中sharp(#)表示墙，空格表示走廊，a,b,c表示鬼：

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

经过一步移动后，地图可以变成如下的样子：

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

输入格式

输入包括最多 $10$ 组数据，每组数据包含一幅地图。输入格式如下：

第一行的 $w，h$ 和 $n$ 表示地图的宽度和高度，$n$ 表示鬼的数目，他们满足 $4 \le w \le 16$，$4 \le h \le 16$，$1 \le n \le 3$。

接下来 $h$ 行，每行 $w$ 个字符：

• 一个 # 表示墙。
• 一个小写字母表示鬼的初始位置（该位置也是走廊）。
• 一个大写字母表示鬼的目标位置（该位置也是走廊）。
• 一个空格表示空的走廊。

在每幅地图里，前 $n$ 个小写字母和前 $n$ 个大写字母表示鬼的初始位置及鬼的目标位置。我们需要将小写字母表示的鬼移动到对应的大写字母的位置里。

最后一组数据后一行有三个 $0$。

输出格式

对每组数据输出一行一个整数，表示最小的移动步数。

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

7
36
77