AT_abc020_c.[ABC020C] 壁抜け

有一个由 $H$ 行 $W$ 列正方形格子组成的网格。每个格子被涂成白色或黑色，其中有两个白色格子分别被指定为起点和终点。

高桥君希望从起点出发，在 $T$ 秒以内到达终点。高桥君可以从当前格子向上下左右相邻的格子移动。如果移动到的是白色格子，则花费 $1$ 秒；如果移动到的是黑色格子，则花费 $x$ 秒（移动前格子的颜色不会影响移动时间）。这里，$x$ 的值需要你在高桥君出发前选择，且 $x$ 必须是正整数，出发后不能更改。

请你求出使得高桥君能够在 $T$ 秒以内到达终点的最大的正整数 $x$。

输入从标准输入读入，格式如下：

$H$ $W$ $T$
$s_{1,1} s_{1,2} \ldots s_{1,W}$
$s_{2,1} s_{2,2} \ldots s_{2,W}$
$\vdots$
$s_{H,1} s_{H,2} \ldots s_{H,W}$

• 第 $1$ 行包含三个整数 $H$、$W$、$T$（$2 \leq H, W \leq 10$，$2 \leq T \leq 10^9$），分别表示格子的行数、列数和高桥君的目标时间。

• 第 $2$ 行到第 $H+1$ 行，每行有 $W$ 个字符，描述每个格子的情况。第 $i+1$ 行第 $j$ 个字符 $s_{i,j}$ 表示第 $i$ 行第 $j$ 列的格子。各字符含义如下：

  • . ：既不是起点也不是终点的白色格子
  • S ：被指定为起点的白色格子
  • G ：被指定为终点的白色格子
  • # ：黑色格子

  其它字符不会出现，且 S 和 G 各出现恰好一次。保证输入数据满足：至少需要经过一次黑色格子才能从起点到终点，且当 $x=1$ 时能够在 $T$ 秒以内到达终点。

输出一个正整数，表示高桥君能够在 $T$ 秒以内到达终点的最大的 $x$。

请不要忘记输出末尾的换行符。

部分分

本题设置了部分分。

• 有 $40$ 分的测试点满足 $2 \leq H, W \leq 3$，$2 \leq T \leq 30$。
• 另有 $30$ 分的测试点满足 $2 \leq T \leq 30$。

（※ 问题 D 也设置了部分分，请一并参考。）

样例解释 1

用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。当 $x=8$ 时，按 $(1, 1) \to (2, 1) \to (2, 2) \to (2, 3)$ 路径移动，可以在 $1+8+1=10$ 秒内到达终点。当 $x \geq 9$ 时，无法在 $10$ 秒内到达终点。

样例解释 2

从起点向右直走，可以在 $2x+1$ 秒内到达终点。虽然绕远路可以减少经过黑色格子的次数，但对于某些 $x$ 的值反而会花费更多时间。

由 ChatGPT 4.1 翻译