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$ 个糖果格子。 Takahashi 现在位于起点格子。 他可以重复移动到上下左右相邻的非墙格子。 他想在不超过 $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$。 否则，输出他在必须结束于终点格子的路上最多可以访问的糖果格子数。

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

1

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

提示

$1\leq H,W \leq 300$ $1 \leq T \leq 2\times 10^6$ $H$、$W$ 和 $T$ 是整数。 $A_{i,j}$ 是 $S$、$G$、$.$、#$和$o$中的一种。 恰有一对$(i,j)$满足$A_{i,j}=S$。 恰有一对$(i,j)$满足$A_{i,j}=G$。 最多 $18$ 对 $(i,j)$ 满足 $A_{i,j}=o$。如果他按 $(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)$ 做五步以访问两个糖果格子是无效的，因为他不会在终点格子结束。
他无法在一步或更少步数内到达终点格子。

标签: AtCoder|abc301E

来源

AtCoder|abc301E