迷宫出逃 程序如何来编写呢

Problem Description
小明又一次陷入了大魔王的迷宫,在无人机的帮忙下,小明获得了整个迷宫的草图。

不同于一般的迷宫,魔王在迷宫里安置了机关,一旦触碰,那么四个方向所在的格子,将翻转其可达性(原先可通过的格子不可通过,反之亦然,机关可以反复触发)。为了防止小明很容易地出逃,魔王在临走前把钥匙丢在了迷宫某处,只有拿到钥匙,小明才能开门在出口处离开迷宫。

万般无奈之下,小明想借助聪明的你,帮忙计算是否有机会离开这个迷宫,最少需要多少时间。(每一单位时间只能向四邻方向走一步)

Input
第一行为 T,表示输入数据组数。

下面 T 组数据,对于每组数据:

第一行是两个数字 n, m(2 < n * m <= 64),表示迷宫的长与宽。

接下来 n 行,每行 m 个字符,‘.’表示空地可以通过,‘x’表示陷阱,‘*’表示机关,‘S’代表起点,‘E’代表出口,‘K’表示钥匙(保证存在且只有一个)。

Output
对第 i 组数据,输出

Case #i:

然后输出一行,仅包含一个整数,表示最少多少步能够拿到钥匙并走出迷魂阵,如果不能则打出-1。

Sample Input
5
5 7
...*x..
...x...
xEx....
x...K.
.x
...S
5 7
K..*x..
...x...
xEx....
x.....
.x
...S
5 7
..K*x..
..*x*..
xEx....
x.....
.x
...S
5 7
..K*x..
.*xx*..
E....
xx.....
.x*...S
4 4
S*..
**..
...E
...K

Sample Output
Case #1:
11
Case #2:
13
Case #3:
13
Case #4:
11
Case #5:
-1

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
用Java做算法提高 学霸的迷宫
0
迷宫的遍历的算法在数据结构方面的一个运用,怎么采用C程序的语言的技术设计的代码实现?
0
c语言,迷宫问题,救救孩子
2
为什么到最后一直无法输出迷宫路径?
0
迷宫的绕路的一个算法问题,如何运用C语言的程序的编写的方式实现
0
数组走到右上角时可以获得的最大金币数目,请问怎么样才能使用C语言的程序的编写的技术实现的?
0
一个迷宫的便利的典型的算法问题,怎么利用C语言程序代码思路解题的过程?
0
数字的迷宫的寻路的算法解决,怎么采用c程序的语言编写的技术实现的呢?
0
走到右上角时可以获得的最大金币数目的运算,怎么采用C程序的语言代码编写技术去实现的呢?
0
迷宫的寻找的路线的问题,要求使用C语言的程序的编写的设计的代码的过程的做法怎么才能实现的呢?
0
计算以最小化离开迷宫的预期步数,怎么才能采用C语言的程序的设计的代码的编写的过程的设计的实现的原理
0
迷宫的寻找的路线的问题,要求使用C语言的程序的编写的设计的代码的过程的做法的实现
0
迷宫输出要通过的最短命令序列,怎么使用C语言的程序的解决的思路去编写程序的代码的
1
迷宫问题return;到底是返回到哪一步?
0
逃离迷宫的策略用程序实现
0
Line & Circle Maze 迷宫的问题
1
走迷宫问题求救!急!
1
c语言迷宫问题怎么解??
0
新型全连通迷宫问题求解
1
迷宫问题的代码看不懂了,求大佬注释