万圣节后的早晨_NOI导刊2010提高(03)

题目描述

要求你写一个程序,在一个地图中,找到最小步数将每个鬼移动到他们指定的位置。地图包含一些小方格。每格要么是墙(鬼不能进入),要么是走廊(鬼能进入)。 每一步里,你可以同时移动任意数量的鬼。每个鬼要么待在原地不动,要么移动到相邻的格子里(相邻的格子有公共边),如果移动满足下列条件,则移动是可行的。 1.没有一个以上的鬼在同一个格子里。 2.没有一对鬼在一步里交换了位置。 例如,假设鬼的位置是如右上图所示的,其中sharp(#)表示墙,空格表示走廊,a,b,c表示鬼: ```cpp #### ab# #c## #### ``` 经过一步移动后,地图可以变成如下的样子: ```cpp #### #### #### #### ab# a b# acb# ab # #c## #c## # ## #c## #### #### #### #### ```

输入输出格式

输入格式


输入包括最多10组数据,每组数据包含一幅地图。输入格式如下: ![](https://cdn.luogu.com.cn/upload/pic/621.png) 第一行的w,h和n表示地图的宽度和高度,n表示鬼的数目,他们满足: 4≤w≤16,4≤h≤16,1≤n≤3 接下来h行,每行w个字符: 一个#表示墙。 一个小写字母表示鬼的初始位置(该位置也是走廊)。 一个大写字母表示鬼的目标位置(该位置也是走廊)。 一个空格表示空的走廊。 在每幅地图里,前n个小写字母和前n个大写字母表示鬼的初始位置及鬼的目标位置。我们需要将小写字母表示的鬼移动到对应的大写字母的位置里。 最后一组数据后一行有三个0。

输出格式


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

输入输出样例

输入样例 #1

[pic=622]

输出样例 #1