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 翻译