August 8 – 15, Plovdiv, Bulgaria

Contest Day 2 - Mecho

English 1.1

MECHO

Mecho the bear has found a little treasure – the bees’ secret honeypot, which is full of honey! He
was happily eating his newfound treasure until suddenly one bee saw him and sounded the bee
alarm. He knows that at this very moment hordes of bees will emerge from their hives and start
spreading around trying to catch him. He knows he has to leave the honeypot and go home
quickly, but the honey is so sweet that Mecho doesn’t want to leave too soon. Help Mecho
determine the latest possible moment when he can leave.

Mecho’s forest is represented by a square grid of N by N unit cells, whose sides are parallel to
the north-south and east-west directions. Each cell is occupied by a tree, by a patch of grass, by
a hive or by Mecho’s home. Two cells are considered adjacent if one of them is immediately to
the north, south, east or west of the other (but not on a diagonal). Mecho is a clumsy bear, so
every time he makes a step, it has to be to an adjacent cell. Mecho can only walk on grass and
cannot go through trees or hives, and he can make at most S steps per minute.

At the moment when the bee alarm is sounded, Mecho is in the grassy cell containing the
honeypot, and the bees are in every cell containing a hive (there may be more than one hive in
the forest). During each minute from this time onwards, the following events happen in the
following order:

• If Mecho is still eating honey, he decides whether to keep eating or to leave. If he
continues eating, he does not move for the whole minute. Otherwise, he leaves
immediately and takes up to S steps through the forest as described above. Mecho
cannot take any of the honey with him, so once he has moved he cannot eat honey again.

• After Mecho is done eating or moving for the whole minute, the bees spread one unit
further across the grid, moving only into the grassy cells. Specifically, the swarm of bees
spreads into every grassy cell that is adjacent to any cell already containing bees.
Furthermore, once a cell contains bees it will always contain bees (that is, the swarm
does not move, but it grows).

In other words, the bees spread as follows: When the bee alarm is sounded, the bees only
occupy the cells where the hives are located. At the end of the first minute, they occupy all
grassy cells adjacent to hives (and still the hives themselves). At the end of the second minute,
they additionally occupy all grassy cells adjacent to grassy cells adjacent to hives, and so on.
Given enough time, the bees will end up simultaneously occupying all grassy cells in the forest
that are within their reach.

Neither Mecho nor the bees can go outside the forest. Also, note that according to the rules
above, Mecho will always eat honey for an integer number of minutes.

The bees catch Mecho if at any point in time Mecho finds himself in a cell occupied by bees.

August 8 – 15, Plovdiv, Bulgaria

Contest Day 2 - Mecho

English 1.1

TASK
Write a program that, given a map of the forest, determines the largest number of minutes that
Mecho can continue eating honey at his initial location, while still being able to get to his home
before any of the bees catch him.

EXAMPLES

Sample Input

Sample Output
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT
1

After eating honey for one minute, Mecho can take the shortest path directly to the right and he
will be home in another two minutes, safe from the bees.

Sample Input

Sample Output
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT
2

After eating honey for two minutes, Mecho can take steps →↑→ during the third minute, then
steps →→→ during the fourth minute and steps ↓→ during the fifth minute.

1 ≤ N ≤ 800
The size (side length) of the map
1 ≤ S ≤ 1,000
The maximum number of steps Mecho can take in each minute

Your program must read from standard input the following data:
• The first line contains the integers N and S, separated by a space.
• The next N lines represent the map of the forest. Each of these lines contains N characters
with each character representing one unit cell of the grid. The possible characters and their
associated meanings are as follows:
T denotes a tree
G denotes a grassy cell
M denotes the initial location of Mecho and the honeypot, which is also a grassy cell
D denotes the location of Mecho’s home, which Mecho can enter, but the bees cannot.
H denotes the location of a hive

NOTE: It is guaranteed that the map will contain exactly one letter M, exactly one letter D and
at least one letter H. It is also guaranteed that there is a sequence of adjacent letters G that
connects Mecho to his home, as well as a sequence of adjacent letters G that connects at
least one hive to the honeypot (i.e., to Mecho’s initial location). These sequences might be as
short as length zero, in case Mecho’s home or a hive is adjacent to Mecho’s initial location.
Also, note that the bees cannot pass through or fly over Mecho’s home. To them, it is just like
a tree.

Your program must write to standard output a single line containing a single integer: the
maximum possible number of minutes that Mecho can continue eating honey at his initial
location, while still being able to get home safely.

If Mecho cannot possibly reach his home before the bees catch him, the number your program
writes to standard output must be -1 instead.

GRADING
For a number of tests, worth a total of 40 points, N will not exceed 60.

August 8 – 15, Plovdiv, Bulgaria

Contest Day 2 - Mecho

English 1.1

생성자가 기록되지 않았습니다.

출처 IOI 2009