P1778 万圣节后的早晨

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

输入包括最多 $10$ 组数据，每组数据包含一幅地图。输入格式如下： $$\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}$$ 第一行的 $w，h$ 和 $n$ 表示地图的宽度和高度，$n$ 表示鬼的数目，他们满足 $4 \le w \le 16$，$4 \le h \le 16$，$1 \le n \le 3$。 接下来 $h$ 行，每行 $w$ 个字符： - 一个 `#` 表示墙。 - 一个小写字母表示鬼的初始位置（该位置也是走廊）。 - 一个大写字母表示鬼的目标位置（该位置也是走廊）。 - 一个空格表示空的走廊。 在每幅地图里，前 $n$ 个小写字母和前 $n$ 个大写字母表示鬼的初始位置及鬼的目标位置。地图的最外层是墙壁，即地图的第一行和最后一行的所有字符都是`#`，每一行的第一个字符和最后一个字符也都是`#`。保证地图上的所有走廊都是连通的，同样所有墙壁也是连通的。地图上每个 $2 \times 2$ 的区域都至少有一个格子为墙（`#`）。 我们需要将小写字母表示的鬼移动到对应的大写字母的位置里。 最后一组数据后一行有三个 $0$。

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