AT_abc301_e [ABC301E] Pac-Takahashi

有一个 $H$ 行 $W$ 列的网格。自上而下第 $i$ 行，自左而右第 $j$ 列的格子记作 $(i,j)$。每个格子可能是起点、终点、空地、墙或者糖果格。$(i,j)$ 的类型由字符 $A_{i,j}$ 表示，$A_{i,j}=$ `S` 表示起点，$A_{i,j}=$ `G` 表示终点，$A_{i,j}=$ `.` 表示空地，$A_{i,j}=$ `#` 表示墙，$A_{i,j}=$ `o` 表示糖果格。保证起点和终点各有且仅有一个，糖果格最多有 **18 个**。 高桥君现在在起点。他可以多次移动到上下左右相邻且不是墙的格子。高桥君希望用不超过 $T$ 次移动到达终点。请判断是否可能做到。如果可能，请在最终停在终点的前提下，求出途中最多能访问多少个不同的糖果格。注意，同一个糖果格多次经过只计一次。

输入通过标准输入给出，格式如下： > $H$ $W$ $T$ > $A_{1,1}A_{1,2}\dots A_{1,W}$ > $\vdots$ > $A_{H,1}A_{H,2}\dots A_{H,W}$

如果无法在 $T$ 步内到达终点，输出 `-1`。如果可以，请输出在最终停在终点的前提下，途中最多能访问的不同糖果格数量。

## 限制条件 - $1 \leq H, W \leq 300$ - $1 \leq T \leq 2 \times 10^6$ - $H, W, T$ 均为整数 - $A_{i,j}$ 只可能是 `S`, `G`, `.`, `#`, `o` 之一 - 满足 $A_{i,j}=$ `S` 的 $(i,j)$ 仅有一个 - 满足 $A_{i,j}=$ `G` 的 $(i,j)$ 仅有一个 - 满足 $A_{i,j}=$ `o` 的 $(i,j)$ 最多有 **18 个** ## 样例解释 1 如 $(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3)$，移动 $4$ 次，可以访问 $1$ 个糖果格并最终到达终点。无法在 $5$ 步内访问 $2$ 个糖果格并最终到达终点，所以答案是 $1$。注意，如果 $(1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3)$，虽然经过 $2$ 个糖果格，但最后不在终点，因此不合法。 ## 样例解释 2 无法在 $1$ 步内到达终点。 由 ChatGPT 4.1 翻译