题目描述

$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 のときお菓子マスです。 ここで、スタートマスとゴールマスはちょうど $1$ つずつあり、お菓子マスは $18$ 個以下であることが保証されます。

高橋くんは現在スタートマスにいます。 高橋くんは、上下左右に隣接するマスであって壁マスでないマスに移動することを繰り返し行えます。 高橋くんは今から $T$ 回以下の移動によってゴールマスに到達したいです。 そのようなことは可能かどうか判定してください。 可能な場合は、最終的にゴールマスにいるという条件のもとで、移動の途中に訪れるお菓子マスの数の最大値を求めてください。 ただし、$1$ つのお菓子マスに複数回訪れた場合でも、カウントするのは $1$ 回のみです。

输入格式

入力は以下の形式で標準入力から与えられる。

$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 を出力せよ。 可能ならば、最終的にゴールマスにいるという条件のもとで、移動の途中に訪れるお菓子マスの数の最大値を出力せよ。

题目大意

给定一张地图，S 代表起点，G 代表终点，. 代表路，# 代表墙，o 代表猴子。

现在你从起点出发，每次能用 $1$ 个单位时间，向相邻的非墙格子移动。猴子不会移动。

求出在 $T$ 个单位时间内从起点到终点，且在此基础上抓到的猴子最多。求出抓到的最多猴子数。如果时间内连终点都达不到，输出 $-1$。

数据保证猴子的数量不超过 $18$。

translated by

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 のいずれか
• $A_{i,j}=$ S を満たす $(i,j)$ の組がちょうど $1$ つ存在する
• $A_{i,j}=$ G を満たす $(i,j)$ の組がちょうど $1$ つ存在する
• $A_{i,j}=$ o を満たす $(i,j)$ の組は $18$ 個以下

Sample Explanation 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) $ と移動すると $5$ 回の移動で $2$ 個のお菓子マスを訪れることができますが、最終的にゴールマスにいないため無効であることに注意してください。

Sample Explanation 2

$1$ 回以下の移動でゴールマスに到達することはできません。