← 返回题目列表

AtCoder · abc020_c

C. 穿墙

中文机器翻译题面 查看原题

問題文

方形单元格是垂直的 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_{i,j} , 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