You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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$。

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