2070. 万圣节后的早晨

【问题描述】

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

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

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

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

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

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

【输入格式】

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

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

4≤w≤16, 4≤h≤16, 1≤n≤3

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

一个#表示墙。

一个小写字母表示鬼的初始位置（该位置也是走廊）。

一个大写字母表示鬼的目标位置（该位置也是走廊）。

一个空格表示空的走廊。

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

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

【输出格式】

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

【样例输入】 [蒟蒻自己调不好这个缩进，所以在其他编辑器上截了图，可以去POJ上复制样例 →.→]

【样例输出】

7

36

【来源】

Japan 2007 Uva 1601 POJ 3523 刘汝佳 《算法竞赛入门经典》 例题 7-9 （P205）