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.

题目描述

名人小 Z 是很低调的，小 Z 和小 Y 正在专心吃饭。猛然得到最新消息，有若干狗仔团队正闻讯蜂拥而来。

小 Z 真是不理解现在这些人对八卦的渴望怎么那么大，但是，今天小 Z 真不想放弃美味的饭菜，那么就只能尽可能多呆一些时间用来吃饭，小 Z 希望在不会被狗仔队抓拍到的前提下吃饭的时间越长越好。

小 Z 吃饭所在的城市可以看做是 $N$ 行 $N$ 列的方格，每一个格子的类型为 $a_{i,j}$，有如下几种情况：

1. T，表示这个格子是一个私人住宅建筑物

2. G，表示这个格子是一块空地

3. M，表示这个格子是小 Z 正在吃饭的地方，当然也可以看成是一个空地或者公共（非私人）建筑物

4. D，表示这个格子是小 Z 的家

5. H，表示这个格子是一个狗仔队的窝点

我们认为两个格子如果有相同的边，那么就是相邻的，即上下左右的格子是相邻的。

小 Z 和狗仔队每次走的时候，只会走相邻的格子，且谁都不会闯到其他人私有的建筑物里。小 Z 每一秒至多走 $S$ 步，由于小 Z 有职业赛车手小 W 当专门司机，$S$ 的值可能很大。

当小 Z 得知狗仔队将至的消息时，狗仔队都在各自窝点。随着时间的推移，每一秒都会按照如下的顺序发生着一些事件：

1. 如果小 Z 还在吃饭地点，那么他可以选择现在这一秒吃饭，或者开始逃跑

   • 如果是继续吃饭，那么这一秒小 Z 是不会移动的，如果逃跑，那么接下来小 Z 可以在城市里移动不超过 $S$ 步。一旦离开了，小 Z 就会一直不停的逃跑。如果在某个位置遇到了狗仔那么小 Z 就会被抓拍

2. 当小 Z 选择继续吃饭或者选择移动后，所有的狗仔队会向四周更远的格子移动一步，并且一旦狗仔队走到了一个格子，就会派一个狗仔留守在那里。最开始的时候，狗仔队占据了所有狗仔窝点所在的格子。

   • 例如，小 Z 第 $1$ 秒选择留在原地，狗仔队第 $1$ 秒会向四周扩散，如果遇到了小 Z，小 Z 就被抓拍到了

   • 如果小 Z 开始在 $(1,1)$，$S$ 为 $2$，并且第 $1$ 秒选择移动，那么小 Z 可以在第一秒移动到 $(1,2),(1,3)$ 格子，假设狗仔队第 $1$ 秒可以来到 $(1,2)$ 格子，这个时候，小 Z 也可以通过 $(1,2)$ 格子，因为狗仔队是在小 Z 选择停留或者移动后进行扩散，小 Z 在 $1$ 秒末的时候可以走到 $(1,3)$ 格子，不会遇到狗仔队；如果狗仔队在第 $1$ 秒可以来到 $(1,3)$ 格子，那么小 Z 就不能走 $(1,3)$ 格子。

   • 换句话说，狗仔队总是在小 Z 决定停留还是移动后进行扩散，小 Z 每一秒所在的位置如果不是家，要保证狗仔队这一秒不能在这个位置。

狗仔和小 Z 都不能走出城市的边缘，且狗仔队是无法占领小 Z 的家的，现在小 Z 想知道如果要能够安全回到家，那么他还能够继续吃饭的最长时间是多少？

「出题人的一些善意提示」

1. 小 Z 和狗仔队都不能走到地图的 T 格子，但是他们都可以走到 M 格子。

2. 参照样例认真读题

输入格式

第一行两个整数 $N,S$ 分别表示城市的大小和小 Z 每一秒的移动的最大距离。

接下来 $N$ 行每行 $N$ 个字符，其中 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列格子的具体情况，$a_{i,j}$ 是字符 T、G、M、D、H 这 $5$ 种中的一种，具体含义见题目。

输出格式

一行一个整数，表示小 Z 最多还能继续吃饭多长时间。

如果小 Z 不可能回到家了，那么就输出 -1。

样例 #1

样例输入 #1

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT

样例输出 #1

2

提示

【样例解释】

对于样例，一种可行的方法是，停留两秒钟。

1. 然后第 $3$ 秒走三步到 $(3,3)$

2. 第 $4$ 秒走三步到 $(3,6)$

3. 第 $5$ 秒走两步到 $(4,7)$ 中途不会遇到狗仔队

【数据范围】

对于 $30\%$ 的数据满足 $S=1$。

对于 $50\%$ 的数据满足 $N≤60$

对于 $100\%$ 的数据 $1≤N≤800,1≤S≤1000$，并且保证地图中的 $a_{i,j}$ 有且仅有一个 M，一个 D，并保证至少有一个 H。同样的，保证一定存在一条能够从 G 走到 M 的路。