994. [NOIP 2010冲刺三]鬼屋惊魂

【题目描述】

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

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

1. 没有一个以上的鬼在同一个格子里。

2. 没有一对鬼在一步里交换了位置。

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

####

 ab#

#c##

####

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

#### #### #### ####

  ab# a b# acb# ab  #

#c## #c## # ## #c##

#### #### #### ####

【输入格式】

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

第一行的 w ， h 和 n 表示地图的宽度和高度， n 表示鬼的数目，他们满足：

4 ≤ w ≤ 16, 4 ≤ h ≤ 16, 1 ≤ n ≤ 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