分数: 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