题目背景

IOI2009 D2T2

题目描述

小熊 Mecho 发现了一个宝藏 —— 蜜蜂的秘密蜜罐，里面装满了蜂蜜！他高兴地吃着他的新发现的宝藏，直到突然有一只蜜蜂看到了他，并发出了警报。他知道就在这个时刻，成群的蜜蜂会从蜂巢里出来，开始四处蔓延，试图抓住他。他知道他必须离开蜜罐，尽快回家，但蜂蜜太甜了， Mecho 不想太早离开。帮 Mecho 确定他最晚什么时候可以离开。

Mecho 所在的森林是 $N\times N$ 的正方形网格，其两侧平行于南北和东西方向。每个格子由一棵树、一小块草、一个蜂巢或 Mecho 的家占据。如果两个格子中的一个与另一个的北、南、东或西相邻（但不在对角线上），则认为这两个格子相邻。Mecho 是一只笨拙的熊，所以每次它走一步，都只能移动至相邻的格子。Mecho 只能在草地上行走，不能穿过树木或蜂巢，而且他每分钟最多能走 $S$ 步。

当蜜蜂警报响起的那一刻， Mecho 在装有蜜罐的草格子里，而蜜蜂则在每个包含蜂巢的格子里（森林里可能有不止一个蜂巢）。接下来的每一分钟内，以下事件按顺序发生:

1. 如果 Mecho 还在吃蜂蜜，他会决定是继续吃还是离开。如果它继续吃东西，就会一动不动。否则，他会立即离开，并像上面描述的那样移动至多 $S$ 步。 Mecho 不能带任何蜂蜜，所以一旦他移动了，他就不能再吃蜂蜜了。

2. 当 Mecho 吃完或移动了整整一分钟后，蜜蜂在网格中进一步扩散了一个单位，只移动到草格子中。具体地，蜂群扩散到每一个与任何已经有蜜蜂的格子相邻的草格子。此外，一旦一个格子有蜜蜂，它将永远有蜜蜂（也就是说，蜂群不移动，但它生长）。

换句话说，蜜蜂的分布如下：当蜜蜂警报响起时，蜜蜂只占据蜂巢所在的格子。在第一分钟结束时，它们占据了蜂巢附近所有长满草的格子（以及原本的所有蜂巢）。在第二分钟结束时，它们又占据了和 “与蜂巢相邻的草格子” 相邻的草格子，以此类推。只要有足够的时间，这些蜜蜂就会同时占据森林中它们能到达的所有草格子。

Mecho 和蜜蜂都不能走出森林。另外，根据上面的规则，Mecho 总是吃整数分钟的蜂蜜。

如果 Mecho 发现自己在一个被蜜蜂占据的格子里，蜜蜂就会抓住 Mecho。

任务：编写一个程序，给定一张森林地图，计算出 Mecho 可以在最初的位置继续吃蜂蜜的最长时间，同时还能在任何蜜蜂抓到他之前回到他的家。

输入格式

第一行包含两个由空格隔开的整数 $N, S$，分别表示地图大小和 Mecho 每分钟最多移动的步数。

接下来 $N$ 行描述了森林地图。其中每一行包含 $N$ 个字符，每个字符表示一个格子。可能的字符及其含义如下:

• T 表示树。
• G 表示草格子。
• M 表示 Mecho 的初始位置，也是蜜罐的位置。这是一个草格子，蜜蜂可以进入。
• D 表示 Mecho 的家。Mecho 可以进入这个格子，但蜜蜂不可以。
• H 表示蜂巢。

注意：保证地图恰好包含一个字母 M，恰好一个字母 D 和至少一个字母 H。保证存在相邻的字母 G 形成的路径连接 Mecho 和它的家，以及相邻的字母 G 形成的路径连接蜜罐（即 Mecho 最初的位置）和至少一个蜂巢。这些序列可能长度为零，如 Mecho 的家或蜂巢和 Mecho 的初始位置相邻。另外，蜜蜂不能通过或飞过 Mecho 的家。对它们来说，Mecho 的家就像一棵树。

输出格式

输出一行一个整数，表示 Mecho 最多还能在初始位置吃多少分钟蜂蜜，并安全地回家。

如果 Mecho 不可能在蜜蜂抓住它之前回家，输出 $-1$。

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

1

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT

2

提示

样例解释

• 样例 1：吃了一分钟蜂蜜后，Mecho 可以沿着最短的路径直接往右走，再过两分钟他就可以安全到家了。

• 样例 2：吃了两分钟蜂蜜后，Mecho 可以在第三分钟向右，向上，向右走；在第四分钟向右走三步；在第五分钟向下，向右走。

数据范围与约定

• 对于 $40\%$ 的数据，$N\leq 60$。
• 对于 $100\%$ 的数据，$1\leq N\leq 800$，$1\leq S\leq 1000$。

注意在实际评测中，部分分和以上描述有出入。