小熊Mecho

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file mecho.in Output file mecho.out

问题描述

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

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

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

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

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

    蜜蜂按照如下规则扩散:

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

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

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

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

    任务

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

    数据规模

    lN800    地图的大小(即正方形的边长)

    lSl000    Mecho每分钟可以行走的最大步数。

    输入

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

    第一行包含整数NS,以一个空格隔开。

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

  T表示一棵树木

  G表示草地单元格

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

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

  H表示蜂房的位置

  注意:数据保证地图中只存在一个字符M,一个字符D,至少存在一个字符H。数据保证M可通过一串相邻的字符G到达D,也保证至少存在一个日可以通过一串相邻的G到达M。这串相邻的字符G的长度可以是0,例如,MechoD或者蜂房HMecho的起始位置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分钟走| ->两步回到家里,而不被蜜蜂抓到。