#abc020c. [abc020_c]壁抜け

[abc020_c]壁抜け

问题描述

有一个由 HHWW 列的正方形格子组成的图形。每个格子都被涂成白色或黑色,并且其中两个白色格子分别指定为起点和终点。

高桥君想要从起点出发,在 TT 秒内到达终点。高桥君可以从一个格子上下左右移动到相邻的另一个格子。在移动过程中,如果目标格子是白色格子,则需要花费 11 秒钟;如果目标格子是黑色格子,则需要花费 xx 秒钟(移动前的格子颜色不会影响移动时间)。在高桥君出发前,你需要选择一个 xx 的值。xx 必须为正整数,并且不能在高桥君出发后更改。

请计算出高桥君在 TT 秒内可以到达终点的最大 xx 值。


输入

输入数据以以下格式从标准输入中给出:

HH WW TT s1,1s_{1,1}s1,2s_{1,2} .. s1,Ws_{1,W} s2,1s_{2,1}s2,2s_{2,2} .. s2,Ws_{2,W} : sH,1s_{H,1}sH,2s_{H,2} .. sH,Ws_{H,W}

  • 第一行包含三个整数 H,H, W,W, TT (22 H,H, WW 10,10, 22 TT 10910^9),分别表示格子的行数、列数以及高桥君的目标时间。

  • 第二行到第 H+1H+1 行描述了每个格子的信息。第 i+1i+1 行第 jj 个字符 si,js_{i,j} 表示坐标为 (i,j)(i,j) 的格子的状态。每个字符的含义如下:

    • . : 不是起点也不是终点的白色格子
    • S : 起点白色格子
    • G : 终点白色格子
    • # : 黑色格子

    字符串中除以上字符外不会出现其他字符。同时,SG 分别出现恰好一次。输入数据保证存在最大 xx 值,即至少需要移动一次到黑色格子才能从起点到达终点,并且当 x=1x=1 时,在 TT 秒内可以到达终点。

部分点

本问题有部分得分。

  • 40 分的测试用例满足 22 H,H, WW 3,3, 22 TT 3030
  • 其他 30 分的测试用例满足 22 TT 3030

(※问题 D 也有部分得分,请查看那里的部分描述。)

输出

请将高桥君在 TT 秒内可以到达终点的最大 xx 值输出到标准输出中,末尾包含换行符。


示例1


2 3 10
S##
.#G

输出示例1


8

x=8x=8 时,可以通过 (1,1)(2,1)(2,2)(2,3)(1,1) → (2,1) → (2,2) → (2,3) 的移动方式在 1+8+1=101 + 8 + 1 = 10 秒内到达终点。当 x9x \geq 9 时,无法在 1010 秒内到达终点。


示例2


3 4 7
S##G
.##.
..#.

输出示例2


3

向右直线移动,可以在 2x+12x + 1 秒内到达终点。尽管通过绕路可以减少到黑色格子的移动次数,但是取决于 xx 的值,可能会花费更长的时间。


示例3


4 4 1000000000
S###
####
####
###G

输出示例3


199999999