← 返回题目列表

AtCoder · abc301_e

H. Pac-高桥

中文机器翻译题面 查看原题

分数: 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 糖果方块。

高桥现在在起始广场。 他可以重复移动到垂直或水平相邻的非墙方格。 他最多想到达目标方格 T 移动。 判断是否可以。 如果可能的话,找出他在到达他必须完成的目标方格的途中可以访问的糖果方格的最大数量。 每个糖果方块只计算一次,即使它被访问多次。

约束

  • 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.

输入

输入由标准输入按以下格式给出:

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

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

示例输出 1

1

如果他按照 (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3),他可以访问一个糖果方格并在目标方格结束。 他不能移动 5 步或更少的步来访问两个糖果方格并到达目标方格,所以答案是 1.

请注意,进行五次移动 (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#.

示例输出 2

-1

他无法通过一步或更少的动作到达目标方格。


示例输入 3

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

示例输出 3

18