网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
小熊Mecho
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | mecho.in | 输出文件 | 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安全回到家里而不被蜜蜂抓到的前提下,它可以停留在初始位置吃蜂蜜的最长时间。
数据规模
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分钟走| ->两步回到家里,而不被蜜蜂抓到。