E - Lost Kittens Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は H 行 W 列のグリッドで表される街を歩いています。グリッドの各マスは通行可能な道（.）または建物（#）のいずれかです。マスの座標は (r, c)（r 行目、c 列目、ともに 1 から始まる）で表されます。

高橋君の初期位置はグリッド上で @ と表されるマスにあります。街のあちこちに迷子の子猫が K 匹おり、子猫のいるマスはグリッド上で F と表されています。また、街には動物保護施設が 1 箇所あり、グリッド上で G と表されています。これらのマス（@, F, G）はすべて通行可能であり、どの 2 つも異なる位置にあります。

高橋君は現在いるマスから上下左右に隣接する通行可能なマスへ 1 歩で移動することができます。斜め方向への移動やグリッドの外側への移動はできません。同じマスを何度通ってもかまいません。

高橋君が子猫のいるマスに移動すると、その子猫は自動的に保護され、以降は高橋君と一緒に移動します。子猫のいるマスに移動した際に保護を拒否することはできず、一度保護した子猫を途中で手放すこともできません。子猫を保護する順序に制約はありません。すでに保護済みの子猫がいたマスを再度訪れた場合、何も起こりません。

高橋君の目標は、すべての迷子の子猫を保護した状態で動物保護施設のマスにいることです。途中で動物保護施設のマスを通過することは自由ですが、最終的にすべての子猫を保護した状態で動物保護施設のマスにいる必要があります。

高橋君が初期位置から出発して、すべての子猫を保護し動物保護施設に到達するために必要な総移動歩数の最小値を求めてください。なお、出発時点での移動歩数は 0 です。すべての子猫を保護して動物保護施設に到達することが不可能な場合は -1 を出力してください。

制約

  • 1 \leq H \leq 200
  • 1 \leq W \leq 200
  • 1 \leq K \leq 10
  • グリッド中に @ はちょうど 1 個存在する
  • グリッド中に F はちょうど K 個存在する
  • グリッド中に G はちょうど 1 個存在する
  • S_i（1 \leq i \leq H）は ., #, @, F, G のみからなる長さ W の文字列である
  • H, W, K は整数である

入力

H W K
S_1
S_2
\vdots
S_H
  • 1 行目には、グリッドの行数を表す整数 H、列数を表す整数 W、迷子の子猫の数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目から H 行にわたって、グリッドの各行を表す文字列 S_i（1 \leq i \leq H）が与えられる。
  • S_i は W 文字の文字列であり、各文字は以下のいずれかである。
  • . : 通行可能な空きマス
  • # : 建物（通行不可）
  • @ : 高橋君の初期位置（通行可能）
  • F : 迷子の子猫の位置（通行可能、グリッド全体でちょうど K 個存在する）
  • G : 動物保護施設の位置（通行可能、グリッド全体でちょうど 1 個存在する）

出力

すべての子猫を保護して動物保護施設に到達するために必要な最小の総移動歩数を 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

Score : 433 pts

Problem Statement

Takahashi is walking through a city represented by a grid with H rows and W columns. Each cell of the grid is either a passable road (.) or a building (#). The coordinates of a cell are represented as (r, c) (row r, column c, both 1-indexed).

Takahashi's initial position is the cell marked @ on the grid. There are K lost kittens scattered around the city, and the cells where kittens are located are marked F on the grid. There is also exactly one animal shelter in the city, marked G on the grid. All of these cells (@, F, G) are passable, and no two of them occupy the same position.

Takahashi can move one step at a time from his current cell to an adjacent passable cell in one of the four cardinal directions (up, down, left, right). Diagonal movement and movement outside the grid are not allowed. He may pass through the same cell any number of times.

When Takahashi moves to a cell where a kitten is located, that kitten is automatically rescued and will travel with Takahashi from that point on. He cannot refuse to rescue a kitten when entering its cell, nor can he release a kitten once rescued. There are no restrictions on the order in which kittens are rescued. If he revisits a cell where a kitten has already been rescued, nothing happens.

Takahashi's goal is to be at the animal shelter cell with all lost kittens rescued. He may freely pass through the animal shelter cell along the way, but ultimately he must be at the animal shelter cell with all kittens rescued.

Find the minimum total number of steps required for Takahashi to start from his initial position, rescue all kittens, and reach the animal shelter. The number of steps at the start is 0. If it is impossible to rescue all kittens and reach the animal shelter, output -1.

Constraints

  • 1 \leq H \leq 200
  • 1 \leq W \leq 200
  • 1 \leq K \leq 10
  • There is exactly 1 @ in the grid
  • There are exactly K Fs in the grid
  • There is exactly 1 G in the grid
  • S_i (1 \leq i \leq H) is a string of length W consisting only of ., #, @, F, G
  • H, W, K are integers

Input

H W K
S_1
S_2
\vdots
S_H
  • The first line contains three space-separated integers: H representing the number of rows, W representing the number of columns, and K representing the number of lost kittens.
  • The following H lines each contain a string S_i (1 \leq i \leq H) representing a row of the grid.
  • S_i is a string of W characters, where each character is one of the following:
  • . : A passable empty cell
  • # : A building (impassable)
  • @ : Takahashi's initial position (passable)
  • F : A lost kitten's position (passable, exactly K in the entire grid)
  • G : The animal shelter's position (passable, exactly 1 in the entire grid)

Output

Output in one line the minimum total number of steps required to rescue all kittens and reach the animal shelter. If it is impossible, output -1.

Sample Input 1

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

Sample Output 1

8

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

-1