← 返回题目列表

AtCoder · awc0075_e

E. 丢失的小猫

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

分数: 433 分

问题陈述

高桥正在穿过一座由网格代表的城市, H 行和 W 列。网格的每个单元格要么是一条可通行的道路(.)或建筑物(#)。单元格的坐标表示为 (r, c) (行 r,列 c,均为 1 索引)。

高桥的初始位置是标记的单元格 网格上的 @ 。有 K 走失的小猫散落在城市各处,小猫所在的小区已被标记 网格上的 F 。城市里还有一处动物收容所,标有 网格上的 G 。所有这些细胞(@, F, G) 还可以,并且没有两个占据相同的位置。

高桥可以在四个基本方向(上、下、左、右)之一上从当前单元格一次移动一步到相邻的可通行单元格。不允许对角线移动和网格外移动。他可以多次穿过同一个牢房。

当高桥移动到小猫所在的牢房时,该小猫会自动获救,并从那时起与高桥一起旅行。当小猫进入牢房时,他不能拒绝营救,也不能在营救后释放小猫。小猫被拯救的顺序没有限制。如果他再次来到已经救出一只小猫的牢房,什么也不会发生。

高桥的目标是 到达动物收容所,所有失踪的小猫都被救出。他可以一路自由地通过动物收容所,但最终他必须和所有小猫一起被救到动物收容所。

找到 最小总步数 要求高桥从最初的位置出发,营救所有小猫,并到达动物收容所。开始时的步数为 0。如果无法营救所有小猫并到达动物收容所,则输出 -1.

约束

  • 1 \leq H \leq 200
  • 1 \leq W \leq 200
  • 1 \leq K \leq 10
  • 正是 1 @ 在网格中
  • 正好有 K F位于网格中
  • 正是 1 G 在网格中
  • S_i (1 \leq i \leq H) 是一个长度的字符串 W 仅包含 ., #, @, F, G
  • H, W, K 是整数

输入

H W K
S_1
S_2
\vdots
S_H
  • 第一行包含三个空格分隔的整数: H 代表行数, W 代表列数,以及 K 代表丢失小猫的数量。
  • 以下 H 行每行包含一个字符串 S_i (1 \leq i \leq H) 代表网格的一行。
  • S_i 是一串 W 个字符,其中每个字符是以下字符之一:
  • . :一个可以通过的空单元格
  • # :一座建筑物(无法通行)
  • @ :高桥的初始位置(尚可)
  • F :丢失的小猫的位置(还可以,完全正确) K 在整个网格中)
  • G :动物收容所的位置(还可以,正好 1 在整个网格中)

输出

在一行中输出营救所有小猫并到达动物收容所所需的最少总步数。如果不可能,则输出 -1.


示例输入 1

3 5 2
@.F.G
.....
..F..

示例输出 1

8

示例输入 2

3 5 1
@.#F.
..#..
..#.G

示例输出 2

-1

示例输入 3

7 10 3
@........F
.########.
.#......#.
.#..F...#.
.#......#.
.########.
G........F

示例输出 3

-1