谢谢，麻烦您了！这个问题该如何解答呢？（C++）

[ad_1]

大家好，我在日常练习中遇到了这个问题：

引用：

名人 Z 的麻烦
描述
名人Z非常低调。 Z和Y正在专心致志地吃晚饭。他们刚刚得到最新消息，一些狗仔队正蜂拥而至。
小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.
2、当Z选择继续吃东西或者移动时，所有狗仔队都会绕着格子移动一步，一旦狗仔队到达一个格子，就会派出一名狗仔队停留在那里。一开始，狗仔队占据了所有狗仔队窝点所在的网格。
* 例如，如果小Z在第一秒选择留在原地，狗仔队会在第一秒向四面八方散开，如果遇到小Z，小Z就会被抓到画面中
* 如果小Z从(1,1)开始，S为2，选择在第1秒移动，那么小Z可以在第1秒移动到(1,2),(1,3)格子。假设狗仔队在第1秒就可以来到(1,2)格子，那么此时小Z也可以穿过(1,2)格子，因为狗仔队在小Z选择留下或移动后就扩散了，小Z可以在第一秒结束时到达(1,3)格。 1秒结束，不会遇到狗仔队；如果狗仔队能在1秒结束时来到(1,3)格，那么小Z就无法走到((1,3)格。
* 也就是说，狗仔队总是在小Z决定留还是走后扩散开来，而小Z每一秒都处于一个位置，如果不在家，保证这一秒狗仔队不能在那个位置。
狗仔队和小Z都不能超出城市的边缘，狗仔队也不能占领小Z的家。现在小Z想知道，如果他必须能够安全回家，他最多可以继续吃饭多长时间。
“问题解决者的一些提示
1、小Z和狗仔都不能走到地图的T格，但都可以走到M格。 2.
2. 按照示例仔细阅读问题。

输入格式
第一行包含两个整数，N和S，分别代表城市的大小和小Z每秒可以移动的最大距离。
接下来的N行每行由N个字符组成，其中a(i,j)表示第i行第j列的具体情况。 a(i,j)是T、G、M、D、H 5种字符之一。a(i,j)的含义见标题。

输出格式
连续一个整数，表示Z最多可以继续吃多久。
如果Z无法回家，则输出-1。

样品#1
输入示例#1
7 3
TTTTTTTT
TGGGGGGT
TGGGGGGT
MGGGGGGD
TGGGGT
TGGGGGGT
TGHHGGGT

示例输出#1
2

提示
[Sample Explanation
For the sample, a possible approach is to stay for two seconds.
1. then take three steps to (3,3) at the third second
2. at the 4th second, take three steps to (3,6)
3. take two steps to (4,7) in the 5th second without encountering paparazzi.

[Data Range]

对于 30% 的数据，S=1。
对于50%的数据，N≤60
对于100%的数据1≤N≤800,1≤S≤1000，保证图中a(i,j)有且仅有1个M，1个D，至少1个H。同理，保证一定有一条路径可以从G到M。