迷 宫 带 门 求 解
迷 宫
【问题描述】
迷宫游戏有多种。有的迷宫只要你能走出来就算成功;有的是要求不但能走出来,而且走的步数越少得分越高。为了能得到高分,你肯定在路线的选择上下功夫,尽量用最少的步数走出迷宫。
现有一个迷宫,可以用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
之前 想了 很多我想分步先找钥匙 在从钥匙到门发现 一扇门还可以 多了就挂掉了!