迷 宫 带 门 求 解
迷 宫
【问题描述】
迷宫游戏有多种。有的迷宫只要你能走出来就算成功；有的是要求不但能走出来，而且走的步数越少得分越高。为了能得到高分，你肯定在路线的选择上下功夫，尽量用最少的步数走出迷宫。
现有一个迷宫，可以用M行N列的矩阵来描述，迷宫中有以下6种标志：
（1）$ ：代表你所在的初始位置；
（2）& ：迷宫的出口位置；
（3）# ：墙，无法通过；
（4）. ：地面，可以通过；
（5）A、B、C、...、Z ：每个大写字母代表一个门，可以用对应的小写字母的钥匙打开。
（6）a、b、c、...、z ：每个小写字母代表一把钥匙，可以打开相应大写字母对应的门。
迷宫说明：
（1）迷宫的四周都有墙，所以你无法走出这片M*N的区域，只能从出口’&’处离开迷宫；
（2）在迷宫中你只能向东西南北四个方向走（当然有墙的地方你无法达到；如果没有相应的钥匙，有门的地方你也无法到达）。
（3）如果能走到有小写字母（钥匙）的位置，你就可以拿到它，并用来打开相应大写字母的门，钥匙a只能开A门，钥匙b只能开B门，……
如下列迷宫
最快走出迷宫的方法是：从初始位置$走12步到达钥匙a处拿到钥匙后，然后再走5步到达A处，打开门A后再走1步到达出口&，共走了12+5+1=18步。
上述迷宫中，如果你拿不到钥匙a，就无法打开门A,也就到不了出口。
有的迷宫可能不需要走有门的地方，就能最快走到迷宫出口。
你的任务是，计算出走出迷宫需要的最少步数是多少？
【输入格式】
第1行两个正整数M和N，表示迷宫的长和宽；
第2行一个正整数P，表示门和钥匙的数量（钥匙和门的标号只会出现字母表的前P个字母，如p=2，则只出现钥匙a,b和门A,B）。
第3行至第M+2行，描述整个迷宫。
【输出格式】
一个整数，为走出迷宫需要的最少步数或-1（如果不可能走出迷宫）。
【输入输出样例1】
maze.in
maze.out
5 5
1
&A..$
#.##.
...#.
.#.#.
a#...
18
【输入输出样例2】
maze.in
maze.out
1 4
1
&aA$
-1
之前 想了 很多我想分步先找钥匙 在从钥匙到门发现 一扇门还可以 多了就挂掉了！
