当前没有测试数据。

E - Pac-Takahashi

得分 : $475$ 分

题目描述

我们有一个 $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$ 个糖果方格。

现在，Takahashi 在起始方格，并且他每一步可以在垂直或者水平方向上移动到相邻的非墙方格。 他希望在至多 $T$ 步内到达目标方格。 判断是否可能，如果可能，在到达目标方格的过程中，他最多能经过多少个糖果方格，且结束时必须在目标方格上。 每个糖果方格只计数一次，即使经过多次。

约束条件

• $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。
• 恰好有一个方格满足 $A_{i,j}=$ G。
• 最多有 $18$ 个方格满足 $A_{i,j}=$ o。

输入

从标准输入中以以下格式给出：

$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。 否则，输出在到达目标方格的过程中最多能经过多少个糖果方格，且结束时必须在目标方格上。

3 3 5
S.G
o#o
.#.

1

如果他的移动路径为 $(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3)$，那么他能访问到一个糖果方格，并且最终停留在目标方格上。 他无法在四步内访问到两个糖果方格且最终停留在目标方格上，所以答案是 $1$。

注意，路径 $(1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3)$ 的五步是无效的，因为它没有停留在目标方格上。

3 3 1
S.G
.#o
o#.

-1

他无法在一步或者更少的步数内到达目标方格。

5 10 2000000
S.o..ooo..
..o..o.o..
..o..ooo..
..o..o.o..
..o..ooo.G

18