CTOI09_1  IOI2009 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 northsouth and eastwest 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.
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.
Constraints
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.
Input
The input contains several testcases.
The fist line contains the number of testcase T.
Each testcase has the form as following:
 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.
Output
For each test, 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.
Example
For the input data:
1 7 3 TTTTTTT TGGGGGT TGGGGGT MGGGGGD TGGGGGT TGGGGGT THHHHHT
the correct result is:
1
Explanation of the example: 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.
For the input data:
1 7 3 TTTTTTT TGGGGGT TGGGGGT MGGGGGD TGGGGGT TGGGGGT TGHHGGT
the correct result is:
2
Explanation of the example: 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.
hide comments
weathervane:
20180526 13:52:33
Crucial information such as what to output if Mecho cannot reach home are *image links* not text, which are broken. The two constraints are given below, and 1 is in the pdf linked below. Last edit: 20180526 13:57:18 

hodobox:
20160624 15:02:38
Original statement: http://www.ioi2009.org/GetResource?id=1944


deepak garg:
20150206 07:33:26
what about the input constraints? 

Petar Bosnjak:
20140721 18:24:04
Is everything allright with test data? I am repeadetly getting WA bur really can't find a bug and Im pretty sure my algorithm is correct!What should we output if there is no solution? Last edit: 20140721 18:25:29 

Sourangsu :
20131212 07:19:29
Unexpected AC in first attempt... :O 

:D:
20121112 08:41:38
I don't think it was explicitly removed. I think it was added later than the problem and then it depends in some way on the general language settings for the task. No sure, just speculating. It would probably be too slow here anyway. 

Rocker3011:
20121112 00:34:18
why not let me use PERL 6? 
Added by:  Phan Công Minh 
Date:  20100719 
Time limit:  1.051s1.576s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  IOI 2009 