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。 否则,输出在必须到达终点的前提下,途中最多能经过的糖果格子数。

样例

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

1

如果走 $4$ 步,如 $(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3)$,可以经过 1 个糖果格子并到达终点。 他无法在 5 步或更少步内经过 2 个糖果格子并到达终点,因此答案为 $1$。

注意,走 $5$ 步如 $(1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3)$ 虽然经过了 2 个糖果格子,但由于没有到达终点,所以不合法。

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

-1

他无法在 1 步或更少步内到达终点。

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

18

数据范围

• $1 \le H,W \le 300$
• $1 \le T \le 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。