問題文
方形单元格是垂直的 H 行、横 W 排队。每个方格都涂成白色或黑色,并且白色方格之间 2 分别指定为起点和终点。
高桥从起点开始。 我想在 T 秒内达到目标。高桥可以从每个方格垂直、水平或垂直移动到另一个相邻的方格。此时,如果目的地是一个白色方块, 1 秒,如果是黑色方块 需要 x 秒(移动前方块的颜色不影响移动时间)。在这里, 您将在高桥离开起点之前选择 x 的值。 x 的值必须是正整数,并且在 Takahashi 离开后无法更改。
高桥君 一个正整数,可以在 T 秒内达到目标 找到 x 的最大值。
入力
输入将以以下形式从标准输入给出。
H W T
s_{1,1}s_{1,2} .. s_{1,W}
s_{2,1}s_{2,2} .. s_{2,W}
:
s_{H,1}s_{H,2} .. s_{H,W}
- 1 行中, 3 整数 给出 H, W, T (2 ≦ H, W ≦ 10, 2 ≦ T ≦ 10^9)。这些分别代表方块的行数和列数以及高桥的目标时间。
- 2 从行 H + 1 在该行中,给出了每个方块的信息。 i + 1 线 j 文字目 s_{i,j} 是 i 行 j 对应于列中的正方形。各个字母的含义如下:
.:既未指定为起点也未指定为目标点的白色方块。S:指定为起点的白色方块G:指定为目标点的白色方块#: 黑鳟鱼
S和G分别是 1 一一出现。此外,还保证输入中存在所需的最大值。即至少 1 除非移动到黑色方块,否则不可能从起点出发并到达目标点,并且 当 x = 1 保证可以在 T 秒内到达目标。
部分点
针对此问题设置了部分分数。 满足
- 40 点的测试用例是 2 ≦ H, W ≦ 3, 2 ≦ T ≦ 30 。
- 另一个 30 点的测试用例是 2 ≦ T ≦ 30 。
(*问题D也设置了部分分数。请也检查一下。)
出力
在标准输出中,高桥君 打印 T 秒内达到目标 找到 x 的最大值。
不要忘记最后的换行符。
入力例1
2 3 10 S## .#G
出力例1
8
i 行 j 选择列中的方块。 由 (i, j) 代表。 当 x = 8 时, 当您移动到 (1, 1) → (2, 1) → (2, 2) → (2, 3) 您可以在 1 + 8 + 1 = 10 秒内达到目标。 您无法在 x \geq 9 时, 当您移动到 10 秒内达到目标。
入力例2
3 4 7 S##G .##. ..#.
出力例2
3
从起点一直向右走 您可以在 2x + 1 秒内达到目标。通过绕道,可以减少前往黑色方块的次数,但是 根据 x 的值,可能需要更多时间。
入力例3
4 4 1000000000 S### #### #### ###G
出力例3
199999999