#abc020c. [abc020_c]壁抜け
[abc020_c]壁抜け
问题描述
有一个由 行 列的正方形格子组成的图形。每个格子都被涂成白色或黑色,并且其中两个白色格子分别指定为起点和终点。
高桥君想要从起点出发,在 秒内到达终点。高桥君可以从一个格子上下左右移动到相邻的另一个格子。在移动过程中,如果目标格子是白色格子,则需要花费 秒钟;如果目标格子是黑色格子,则需要花费 秒钟(移动前的格子颜色不会影响移动时间)。在高桥君出发前,你需要选择一个 的值。 必须为正整数,并且不能在高桥君出发后更改。
请计算出高桥君在 秒内可以到达终点的最大 值。
输入
输入数据以以下格式从标准输入中给出:
.. .. : ..
-
第一行包含三个整数 ( ),分别表示格子的行数、列数以及高桥君的目标时间。
-
第二行到第 行描述了每个格子的信息。第 行第 个字符 表示坐标为 的格子的状态。每个字符的含义如下:
.
: 不是起点也不是终点的白色格子S
: 起点白色格子G
: 终点白色格子#
: 黑色格子
字符串中除以上字符外不会出现其他字符。同时,
S
和G
分别出现恰好一次。输入数据保证存在最大 值,即至少需要移动一次到黑色格子才能从起点到达终点,并且当 时,在 秒内可以到达终点。
部分点
本问题有部分得分。
- 40 分的测试用例满足 。
- 其他 30 分的测试用例满足 。
(※问题 D 也有部分得分,请查看那里的部分描述。)
输出
请将高桥君在 秒内可以到达终点的最大 值输出到标准输出中,末尾包含换行符。
示例1
2 3 10
S##
.#G
输出示例1
8
当 时,可以通过 的移动方式在 秒内到达终点。当 时,无法在 秒内到达终点。
示例2
3 4 7
S##G
.##.
..#.
输出示例2
3
向右直线移动,可以在 秒内到达终点。尽管通过绕路可以减少到黑色格子的移动次数,但是取决于 的值,可能会花费更长的时间。
示例3
4 4 1000000000
S###
####
####
###G
输出示例3
199999999