OpenJudge

01:变换的迷宫

总时间限制:
1000ms
内存限制:
65536kB
描述

你现在身处一个R*C 的迷宫中,你的位置用"S" 表示,迷宫的出口用"E" 表示。

迷宫中有一些石头,用"#" 表示,还有一些可以随意走动的区域,用"." 表示。

初始时间为0 时,你站在地图中标记为"S" 的位置上。你每移动一步(向上下左右方向移动)会花费一个单位时间。你必须一直保持移动,不能停留在原地不走。

当前时间是K 的倍数时,迷宫中的石头就会消失,此时你可以走到这些位置上。在其余的时间里,你不能走到石头所在的位置。

求你从初始位置走到迷宫出口最少需要花费多少个单位时间。

如果无法走到出口,则输出"Oop!"

输入
第一行是一个正整数 T,表示有 T 组数据。
每组数据的第一行包含三个用空格分开的正整数,分别为 R、C、K。
接下来的 R 行中,每行包含了 C 个字符,分别可能是 "S"、"E"、"#" 或 "."。
其中,0 < T <= 20,0 < R, C <= 100,2 <= K <= 10。
输出
对于每组数据,如果能够走到迷宫的出口,则输出一个正整数,表示最少需要花费的单位时间,否则输出 "Oop!"。
样例输入
1
6 6 2
...S..
...#..
.#....
...#..
...#..
..#E#.
样例输出
7

01 可改变的邻接矩阵问题<思考BFS的决策>
02 遍历 <注意:大数连接的问题>
03 哈希表<注意不存在的情况>
04 栈<注意0的情况>
05 贪心<注意量变化>

全局题号
10718
添加于
2016-09-07
提交次数
1
尝试人数
1
通过人数
0