S’il te plaît et merci! Comment résoudre cette question ? (C++)

Bonjour les pros, j’ai rencontré cette question lors de la pratique quotidienne :

Citation:

Le problème avec Celebrity Z
Description
Celebrity Z est très discret. Z et Y se concentrent sur leur dîner. Ils venaient tout juste d’apprendre que des équipes de paparazzi pullulaient ici.
Little Z ne comprend vraiment pas pourquoi ces gens ont si faim de potins de nos jours, mais aujourd’hui, Little Z ne veut vraiment pas abandonner son délicieux repas, donc il ne peut rester que le plus longtemps possible pour manger, et il espère pouvoir le faire. manger le plus longtemps possible sans se faire surprendre par les paparazzi.
La ville où Little Z mange peut être considérée comme un réseau carré avec N lignes et N colonnes, et chaque réseau est de type a(i,j) dans les cas suivants :
1. T, indiquant que ce treillis est un immeuble résidentiel privé
2. G, indiquant que cette grille est un terrain vide
3. M, ce qui signifie que ce treillis est l’endroit où le petit Z mange, mais bien sûr il peut aussi être vu comme un terrain vague ou un bâtiment public (non privé)
4. D, indique que ce carré est la maison de Z.
5. H, ce qui signifie que cette cellule est l’antre d’un paparazzi.
Nous considérons que deux grilles sont adjacentes si elles ont les mêmes bords, c’est-à-dire que les grilles supérieure, inférieure, gauche et droite sont adjacentes.
Chaque fois que Little Z et les paparazzi marchent, ils ne marchent que sur les places adjacentes, et aucun d’eux ne s’introduit par effraction dans les bâtiments privés d’autrui. Little Z fait au plus S pas par seconde, et comme Little Z a un pilote de course automobile professionnel, Little W, comme pilote spécial, la valeur de S peut être très grande.
Les paparazzi sont dans leur tanière lorsque Little Z apprend leur arrivée. Au fil du temps, chaque seconde, un certain nombre d’événements se produisent dans l’ordre suivant :
1. Si Little Z est toujours au restaurant, alors il peut choisir de manger maintenant cette seconde, ou commencer à s’enfuir
* S’il doit continuer à manger, alors Petit Z ne bougera pas dans cette seconde, et s’il doit s’enfuir, alors Petit Z ne pourra pas faire plus de S pas autour de la ville dans les prochaines secondes. Une fois parti, Little Z continuera à s’enfuir sans s’arrêter. S’il rencontre un paparazzo à un certain endroit, alors Little Z sera capturé. 2.
2. Lorsque Z choisit de continuer à manger ou de bouger, tous les paparazzi se déplaceront d’un pas plus loin autour de la grille, et une fois que les paparazzi auront atteint une grille, un paparazzi sera envoyé pour y rester. Au tout début, les paparazzi occupent la grille où se trouvent tous les repaires des paparazzi.
* Par exemple, si Petit Z choisit de rester là où il est dans la 1ère seconde, les paparazzi se disperseront dans tous les sens dans la 1ère seconde, et s’ils croisent Petit Z, Petit Z sera pris dans l’image
* Si le petit Z commence à (1,1), S vaut 2 et choisit de se déplacer dans la 1ère seconde, alors le petit Z peut se déplacer vers le réseau (1,2), (1,3) dans la 1ère seconde. En supposant que les paparazzi peuvent atteindre le réseau (1,2) dans la 1ère seconde, alors le petit Z peut également traverser le réseau (1,2) à ce moment-là, car les paparazzi se propagent après que le petit Z ait choisi de rester ou de bouger, et le petit Z peut aller au réseau (1,3) à la fin de la 1ère seconde. au bout d’1 seconde, et ne rencontrera pas les paparazzi ; si les paparazzi peuvent arriver au réseau (1,3) au bout de 1 seconde, alors Little Z ne peut pas aller au réseau ((1,3).
* En d’autres termes, les paparazzi diffusent toujours après que Little Z ait décidé de rester ou de bouger, et Little Z est dans une position à chaque seconde qui, s’il n’est pas chez lui, garantit que les paparazzi ne peuvent pas être dans cette position cette seconde.
Ni les paparazzi ni Little Z ne peuvent dépasser les limites de la ville, et les paparazzi ne peuvent pas s’emparer de la maison de Little Z. Petit Z veut maintenant savoir quelle est la durée maximale pendant laquelle il peut continuer à manger s’il doit pouvoir rentrer chez lui en toute sécurité.
“Quelques conseils du résolveur de problèmes
1. Ni Little Z ni les paparazzi ne peuvent marcher jusqu’à la grille T de la carte, mais ils peuvent tous les deux marcher jusqu’à la grille M. 2.
2. Lisez attentivement la question en suivant l’exemple.

Format d’entrée
La première ligne contient deux nombres entiers, N et S, qui représentent la taille de la ville et la distance maximale que Little Z peut parcourir par seconde.
Les N lignes suivantes sont chacune composées de N caractères, où a(i,j) désigne la situation spécifique de la jème colonne de la i-ème ligne. a(i,j) est l’un des 5 types de caractères T, G, M, D et H. Voir le titre pour la signification de a(i,j).

Format de sortie
Un entier consécutif, indiquant combien de temps Z peut continuer à manger au maximum.
S’il est impossible pour Z de rentrer chez lui, alors affichez -1.

Échantillon n°1
Exemple d’entrée n° 1
7 3
TTTTTTTTT
TGGGGGGT
TGGGGGGT
MGGGGGGD
TGGGGGT
TGGGGGGT
TGHHGGGT

Exemple de sortie n° 1
2

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

Pour 30% des données, S=1.
Pour 50 % des données, N≤60
Pour 100 % des données 1≤N≤800,1≤S≤1000, et assurez-vous que a(i,j) dans la carte a un et un seul M, un D et au moins un H. De même, assurez-vous que il doit y avoir un chemin qui puisse aller de G à M.

Et j’ai vraiment essayé mais je ne sais pas comment le résoudre.

Ce que j’ai essayé :

J’ai essayé BFS, mais comme je suis débutant, je ne sais pas vraiment comment corriger correctement BFS, et je ne sais pas non plus si c’est une pensée correcte ou non.