2134: 迷宫
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：9
解决：4
题目描述
一不小心，小Y同学掉进了一个迷宫里：）迷宫可以用以下描述的M行N列矩阵表示：
|
图标 |
含义 |
|
# |
墙，无法通过 |
|
. |
地面，可以通过 |
|
小写字母（a、b、c、...、z） |
钥匙，可以打开标有对应大写字母的门 |
|
大写字母（A、B、C、...、Z） |
门，可以被标有对应小写字母的钥匙打开 |
|
$ |
小Y的初始位置 |
|
& |
迷宫的出口位置 |
迷宫的四周都有墙，所以小Y无法走出这片M*N的区域，只能从’&’处离开迷宫，且只能向东西南北四个方向走。
作为一个局外人，你的任务是计算出小Y走出迷宫需要的最少步数。
输入
第1行两个正整数M和N，表示迷宫的长和宽；
第2行一个正整数P，表示门和钥匙的数量；
第3行至第M+2行，描述整个迷宫。
输出
输出一行一个整数，为走出迷宫需要的最少步数或-1（如果不可能走出迷宫）。
样例输入 复制
5 5
1
&A..$
####.
...#.
.#.#.
a#...
样例输出 复制
28提示
|
maze.in |
maze.out |
|
5 5 1 &A..$ ####. ...#. .#.#. a#... |
28 |
|
1 4 1 &aA$ |
-1 |
数据规模：
存在10%的数据，P=0；
存在20%的数据，P<=1；
存在40%的数据，P<=2；
对于30%的数据，M,N<=15；
对于100%的数据，1<=M,N<=50，0<=P<=10，保证迷宫中’$’、’&’和所有大小写字母只出现一次，钥匙和门的标号只会出现字母表中的前P个字母。