Background

IOI 2009 D2T2.

Problem Description

The little bear Mecho has found a treasure — the bees’ secret honey jar, full of honey. He happily eats his newly found treasure, until suddenly a bee sees him and raises the alarm. He knows that from this moment on, swarms of bees will come out of their hives and begin spreading through the forest, trying to catch him. He knows he must leave the honey jar and get home as soon as possible, but the honey is so sweet that Mecho does not want to leave too early. Help Mecho determine the latest time he can leave.

The forest where Mecho is located is a square grid of size $N \times N$, with its sides parallel to the north-south and east-west directions. Each cell is occupied by either a tree, a patch of grass, a beehive, or Mecho’s home. Two cells are considered adjacent if one is directly north, south, east, or west of the other (not diagonally). Mecho is a clumsy bear, so each step he takes can only move to an adjacent cell. Mecho can only walk on grass, and cannot pass through trees or beehives, and he can walk at most $S$ steps per minute.

At the moment the alarm is raised, Mecho is in the grass cell that contains the honey jar, and the bees are in every cell that contains a beehive (there may be more than one beehive in the forest). During each subsequent minute, the following events happen in order:

1. If Mecho is still eating honey, he decides whether to keep eating or to leave. If he keeps eating, he does not move at all. Otherwise, he leaves immediately and moves up to $S$ steps as described above. Mecho cannot take any honey, so once he moves, he can no longer eat honey.

2. After Mecho has finished eating or has moved for exactly one full minute, the bees spread one more unit in the grid, moving only into grass cells. Specifically, the swarm spreads to every grass cell adjacent to any cell that already has bees. Also, once a cell has bees, it will have bees forever (that is, the swarm does not move, it grows).

In other words, the bees are distributed as follows: when the alarm is raised, bees occupy only the beehive cells. At the end of the first minute, they occupy all grass cells adjacent to the beehives (as well as all the original beehives). At the end of the second minute, they occupy all grass cells adjacent to the “grass cells adjacent to the beehives”, and so on. Given enough time, the bees will eventually occupy all grass cells in the forest that they can reach.

Neither Mecho nor the bees can leave the forest. Also, according to the rules above, Mecho always eats honey for an integer number of minutes.

If Mecho ever finds himself in a cell occupied by bees, the bees will catch Mecho.

Task: Write a program that, given a forest map, computes the maximum amount of time Mecho can keep eating honey at the starting position, while still being able to return home before any bees catch him.

Input Format

The first line contains two integers $N, S$ separated by a space, representing the map size and the maximum number of steps Mecho can move per minute.

The next $N$ lines describe the forest map. Each line contains $N$ characters, each representing a cell. The possible characters and their meanings are:

• T represents a tree.
• G represents a grass cell.
• M represents Mecho’s initial position, which is also the honey jar position. This is a grass cell, and bees can enter it.
• D represents Mecho’s home. Mecho can enter this cell, but bees cannot.
• H represents a beehive.

Note: It is guaranteed that the map contains exactly one letter M, exactly one letter D, and at least one letter H. It is guaranteed that there exists a path formed by adjacent G cells connecting Mecho to his home, and a path formed by adjacent G cells connecting the honey jar (i.e. Mecho’s initial position) to at least one beehive. These paths may have length zero, for example if Mecho’s home or a beehive is adjacent to Mecho’s initial position. Also, bees cannot pass through or fly over Mecho’s home. To them, Mecho’s home is like a tree.

Output Format

Output one line with one integer: the maximum number of minutes Mecho can still eat honey at the starting position and then get home safely.

If it is impossible for Mecho to get home before the bees catch him, output $-1$.

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

1

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT

2

Hint

Sample Explanation

• Sample 1: After eating honey for one minute, Mecho can go directly right along the shortest path, and after two more minutes he can get home safely.

• Sample 2: After eating honey for two minutes, in the third minute Mecho can go right, up, right; in the fourth minute he can go three steps to the right; in the fifth minute he can go down, right.

Constraints

• For $40\%$ of the testdata, $N \leq 60$.
• For $100\%$ of the testdata, $1 \leq N \leq 800$, $1 \leq S \leq 1000$.

Note that in the actual judging, there are some differences between the subtasks and the description above.

Translated by ChatGPT 5