412. [IOI 2009]小熊Mecho

问题描述

    小熊Mecho发现了一笔小财富——装满蜂蜜的罐子。它正高高兴兴地吃着蜂蜜，突然发现一只蜜蜂看见了自己，并拉响了警报。Mecho知道此刻一群蜜蜂正在从蜂房涌出，并四处涌动试图抓到自己。Mecho知道自己必须赶快离开罐子回到家里，但是蜂蜜实在太好吃了，它不想太早逃离。请你帮助Mecho计算最迟何时离开才能安全地回到家里。

    小熊Mecho所居住的森林可以用正方形网格表示，该正方形网格由N*N个单元格组成，它的边分别平行于南北方向和东西方向。每个单元格被一棵树、一块草地、一个蜂房或者Mecho的家所占据。两个单元格相邻是指它们在南北方向或者东西方向有一条公共边(即对角线上的单元格不是相邻的)。Mecho是一只笨拙的小熊，每步只能从当前单元格走到相邻的单元格，并且它只能走向草地或者家里，不能通过树木或蜂房，它每分钟最多能走s步。

    警报响起的那一刻，Mecho正位于蜂蜜罐所在的单元格，而蜜蜂则分布于各个蜂房所在的单元格内(森林里可能有不止一个蜂房)。这一刻之后，。Mecho按如下规则移动：

    如果Mecho仍在吃蜂蜜，它会决定是继续享用蜂蜜还是开始逃离。如果它决定继续吃蜂蜜，那么在一分钟之内它不会移动。否则，它立刻离开并按照上述要求最多走S步。

Mecho不能带走任何蜂蜜，所以它一旦离开就不能再吃蜂蜜而只能移动了。

    蜜蜂按照如下规则扩散：

    警报响起时，蜜蜂仅仅占据有蜂房的单元格。第一分钟之后，它们占据所有与蜂房所在单元格相邻的草地单元格(包括蜂房所在单元格)。在第二分钟之后，它们多占据了一些草地单元格，即与蜂房相邻的草地单元格的相邻草地单元格，依此类推。只要有充足的时间，蜜蜂可以同时占据它们所能到达的所有草地单元格。

    可以理解为在每一分钟Mecho先移动，蜜蜂后扩散，即Mecho在每一分钟内停留或者移动，而蜜蜂在每分钟结束时瞬间扩散。

    注意：Mecho和蜜蜂都不能走到森林之外。另外，根据上述规则，Mecho吃蜂蜜的时间是一个整数。

    在任何时刻，如果Mecho和蜜蜂处于同一个单元格，即认为蜜蜂抓住了Mecho o．

    任务

    写一个程序，根据给定的森林地图，计算在Mecho安全回到家里而不被蜜蜂抓到的前提下，它可以停留在初始位置吃蜂蜜的最长时间。

    数据规模

    l≤N≤800    地图的大小(即正方形的边长)

    l≤S≤l，000    Mecho每分钟可以行走的最大步数。

    输入

    你的程序必须从标准输入读人下列数据：

    第一行包含整数N和S，以一个空格隔开。

    接下来N行表示森林的地图，其中每行包N个字符，每个字符代表一个单元格。可能出现的字符和它们的相应意义如下：

  T表示一棵树木

  G表示草地单元格

  M表示Mecho的初始位置，即蜂蜜罐所在的位置，该位置是草地单元格

  D表示Mecho的家，这一位置Mecho可以进人，而蜜蜂不能进入

  H表示蜂房的位置

  注意：数据保证地图中只存在一个字符M，一个字符D，至少存在一个字符H。数据保证M可通过一串相邻的字符G到达D，也保证至少存在一个日可以通过一串相邻的G到达M。这串相邻的字符G的长度可以是0，例如，Mecho家D或者蜂房H与Mecho的起始位置M相邻。另外，蜜蜂不能进人或者跳过Mecho家所在的单元格，对它们来说，Mecho的家就像一棵树一样。

    输出

    你的程序必须向标准输出写入一行，该行包含一个整数，表示在安全回家的前提下Mecho可以停留在初始位置吃蜂蜜的最长时间(单位：分钟)。

如果Mecho不能安全回到家里，输出-1。

评分说明

有40分的评测数据，N不大于60。

样例

输入样例

7 3

TTTTTTT

TGGGGGT

TGGGGGT

MGGGGGD

TGGGGGT

TGGGGGT

THHHHHT

输出样例

1

继续吃蜂蜜1分钟后，Mecho可以用2分钟的时间向右走最短路回到家里，而不被蜜蜂抓到。

输入样例

7 3

TTTTTTT

TGGGGGT

TGGGGGT

MGGGGGD

TGGGGGT

TGGGGGT

TGHHGGT

输出样例

2

  继续吃蜂蜜2分钟后，Mecho在第3分钟走-> ^ ->三步，接着在第4分钟走->->->三步，在第5分钟走| ->两步回到家里，而不被蜜蜂抓到。