¡Por favor y gracias! ¿Cómo resolver esta pregunta? (C++)

Hola profesionales, me encontré con esta pregunta durante la práctica diaria:

Cita:

El problema con la celebridad Z
Descripción
La celebridad Z tiene un perfil muy bajo. Z e Y se concentran en la cena. Recién estaban recibiendo las últimas noticias de que algunos equipos de paparazzi están pululando por aquí.
El pequeño Z realmente no entiende cómo estas personas están tan hambrientas de chismes hoy en día, pero hoy, el pequeño Z realmente no quiere renunciar a su deliciosa comida, por lo que solo puede quedarse el mayor tiempo posible para comer y espera poder hacerlo. Come el mayor tiempo posible sin que te pillen los paparazzi.
La ciudad donde come Little Z puede verse como una red cuadrada con N filas y N columnas, y cada red es del tipo a(i,j) con los siguientes casos:
1. T, que indica que esta celosía es un edificio residencial privado
2. G, que indica que esta cuadrícula es un terreno baldío
3. M, lo que significa que esta celosía es el lugar donde come el pequeño Z, pero por supuesto también puede verse como un terreno baldío o un edificio público (no privado).
4. D, denota que este cuadrado es el hogar de Z.
5. H, lo que significa que esta celda es la guarida de los paparazzi.
Consideramos que dos cuadrículas son adyacentes si tienen los mismos bordes, es decir, las cuadrículas superior, inferior, izquierda y derecha son adyacentes.
Siempre que Little Z y los paparazzi caminen, solo caminarán en plazas adyacentes y ninguno de ellos entrará en los edificios privados de otras personas. El pequeño Z da como máximo S pasos por segundo, y dado que el pequeño Z tiene un piloto de carreras profesional, el pequeño W, como conductor especial, el valor de S puede ser muy grande.
Los paparazzi están en sus guaridas cuando Little Z se entera de su llegada. A medida que pasa el tiempo, cada segundo ocurren una serie de eventos en el siguiente orden:
1. Si el pequeño Z todavía está en el lugar para comer, entonces puede elegir comer ahora en este segundo o empezar a huir.
* Si va a seguir comiendo, entonces el Pequeño Z no se moverá en este segundo, y si va a huir, entonces el Pequeño Z no podrá moverse más de S pasos por la ciudad en los próximos segundos. Una vez que se vaya, Little Z seguirá huyendo sin parar. Si se encuentra con un paparazzo en un lugar determinado, Little Z será capturado. 2.
2. Cuando Z elige continuar comiendo o moverse, todos los paparazzi avanzarán un paso más alrededor de la cuadrícula, y una vez que los paparazzi hayan llegado a una cuadrícula, se enviará un paparazzo para que permanezca allí. Al principio, los paparazzi ocupan la cuadrícula donde se encuentran todas las guaridas de paparazzi.
* Por ejemplo, si el Pequeño Z elige quedarse donde está en el primer segundo, los paparazzi se dispersarán en todas direcciones en el primer segundo, y si se encuentran con el Pequeño Z, el Pequeño Z quedará atrapado en la imagen.
* Si la pequeña Z comienza en (1,1), S es 2 y elige moverse en el primer segundo, entonces la pequeña Z puede moverse a la red (1,2), (1,3) en el primer segundo. Suponiendo que los paparazzi pueden llegar a la red (1,2) en el primer segundo, entonces el pequeño Z también puede pasar a través de la red (1,2) en ese momento, porque los paparazzi se dispersan después de que el pequeño Z elige quedarse o moverse, y la pequeña Z puede ir a la red (1,3) al final del primer segundo. al cabo de 1 segundo, y no se encontrará con los paparazzi; Si los paparazzi pueden llegar a la red (1,3) al final de 1 segundo, entonces el pequeño Z no puede ir a la red ((1,3).
* En otras palabras, los paparazzi siempre se difunden después de que Little Z decide si quedarse o moverse, y Little Z está en una posición cada segundo que, si no está en casa, asegura que los paparazzi no puedan estar en esa posición en este segundo.
Ni los paparazzi ni Little Z pueden ir más allá de las afueras de la ciudad, y los paparazzi no pueden apoderarse de la casa de Little Z. Ahora el pequeño Z quiere saber cuál es el tiempo máximo que puede seguir comiendo si quiere poder regresar sano y salvo a casa.
“Algunos consejos amables del solucionador de problemas
1. Ni Little Z ni los paparazzi pueden caminar hasta la cuadrícula T del mapa, pero ambos pueden caminar hasta la cuadrícula M. 2.
2. Lee atentamente la pregunta, siguiendo el ejemplo.

Formato de entrada
La primera línea contiene dos números enteros, N y S, que representan el tamaño de la ciudad y la distancia máxima que Little Z puede moverse por segundo.
Las siguientes N filas están compuestas cada una por N caracteres, donde a(i,j) denota la situación específica de la j-ésima columna de la i-ésima fila. a(i,j) es uno de los 5 tipos de caracteres T, G, M, D y H. Consulte el título para conocer el significado de a(i,j).

Formato de salida
Un número entero seguido, que indica cuánto tiempo Z puede seguir comiendo como máximo.
Si es imposible que Z regrese a casa, entonces genera -1.

Muestra #1
Entrada de muestra n.° 1
7 3
TTTTTTTT
TGGGGGGT
TGGGGGGT
MGGGGGGD
TGGGGGT
TGGGGGGT
TGHHGGGT

Salida de muestra n.° 1
2

Consejos
[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]

Para el 30% de los datos, S=1.
Para el 50% de los datos, N≤60
Para el 100% de los datos 1≤N≤800,1≤S≤1000, y asegúrese de que a(i,j) en el mapa tenga una y solo una M, una D y al menos una H. De manera similar, asegúrese de que debe haber un camino que pueda ir de G a M.

Y realmente lo intenté pero no sé cómo solucionarlo.

Lo que he probado:

Probé BFS, pero como soy principiante, no sé realmente cómo corregir BFS y tampoco estoy seguro de si es un pensamiento correcto o no.