【解決方法】、そしてありがとう！ この質問を解決するにはどうすればよいでしょうか? (C++)

プロの皆さん、毎日の練習中に次のような質問に遭遇しました。

引用：

セレブZのトラブル
説明
セレブZは非常に目立たない。 ZとYは夕食に集中しています。 彼らは、パパラッチチームがここに群がっているという最新ニュースを入手したところだった。
リトル Z は、最近どうして人々がゴシップにそんなに飢えているのか本当に理解できません。でも今日は、リトル Z はおいしい食事を手放したくないので、食べるためにできるだけ長く滞在することしかできず、そうしたいと思っています。パパラッチに捕まらないように、できるだけ長く食べてください。
Little Z が食事をする都市は、N 行 N 列の正方格子として見ることができ、各格子は次の場合の a(i,j) 型になります。
1. T、この格子が個人住宅の建物であることを示します
2. G、このグリッドが空き地であることを示します
3. M、この格子は小さな Z が食事をする場所であることを意味しますが、もちろん、空き地または公共 (非私有) 建物として見ることもできます。
4. D は、この広場が Z の家であることを示します。
5. H、これはこの独房がパパラッチの巣窟であることを意味します。
2 つのグリッドが同じエッジを持つ場合、つまり、上下左右のグリッドが隣接している場合、それらのグリッドは隣接していると見なされます。
リトル Z とパパラッチが歩くときは、隣接する広場だけを歩き、他人の私有建物に侵入することはありません。 リトル Z は 1 秒あたり最大 S ステップを実行します。リトル Z にはプロのレーシング カー ドライバーであるリトル W が特別ドライバーとして付いているため、S の値は非常に大きくなる可能性があります。
リトルZがパパラッチの到着を知ったとき、パパラッチは彼らの巣窟にいた。 時間が経過するにつれて、毎秒いくつかのイベントが次の順序で発生します。
1. リトル Z がまだ食事場所にいる場合、今すぐ食べるか、逃げ始めるかを選択できます。
* 食事を続ける場合、リトル Z はこの秒間動けません。逃げる場合、リトル Z は次の数秒間で街の周りを S 歩しか移動できません。 一度離れてしまうと、リトルZは止まらずに逃げ続けます。 特定の場所でパパラッチに遭遇すると、リトル Z は捕らえられてしまいます。 2.
2. Z が食事の継続または移動を選択すると、すべてのパパラッチはグリッドの周りをさらに 1 歩移動し、パパラッチがグリッドに到達すると、パパラッチがそこに留まるように送られます。 初めに、パパラッチはすべてのパパラッチの巣があるグリッドを占領します。
* たとえば、リトル Z が 1 秒目にその場にとどまることを選択した場合、パパラッチは 1 秒目に四方八方に広がり、リトル Z に遭遇すると、リトル Z が写真に捉えられます。
* 小さな Z が (1,1) から始まり、S が 2 で、1 秒目に移動することを選択した場合、小さな Z は 1 秒目に (1,2)、(1,3) 格子に移動できます。 パパラッチが最初の 1 秒で (1,2) 格子に来ることができると仮定すると、小さな Z が留まるか移動するかを選択した後にパパラッチが広がるため、その時点で小さな Z も (1,2) 格子を通過できます。そして小さな Z は、1 秒目の終わりまでに (1,3) 格子に行くことができます。 1秒後にはパパラッチに遭遇しません。 パパラッチが 1 秒後に (1,3) の格子に来ることができた場合、リトル Z は ((1,3) の格子に行くことはできません。
* 言い換えれば、リトル Z が留まるか移動するかを決定した後、パパラッチは常に拡散し、リトル Z は毎秒その位置にいて、家にいない場合はパパラッチがこの秒その位置にいることはできないことを保証します。
パパラッチもリトル Z も街の端を越えることはできず、パパラッチがリトル Z の家を乗っ取ることもできません。 さて、リトル Z は、安全に家に帰らなければならない場合に、食べ続けられる最長時間を知りたいと考えています。
「問題解決者からの親切なヒント」
1. リトル Z もパパラッチも、マップの T グリッドまでは歩くことができませんが、M グリッドまでは歩くことができます。 2.
2. 例に従って、質問を注意深く読んでください。

入力フォーマット
最初の行には、都市のサイズと Little Z が 1 秒あたりに移動できる最大距離を表す 2 つの整数 N と S が含まれています。
次の N 行はそれぞれ N 文字で構成されます。ここで、a(i,j) は、i 番目の行の j 番目の列の特定の状況を示します。 a(i,j) は、T、G、M、D、H の 5 種類の文字のいずれかです。a(i,j) の意味については、タイトルを参照してください。

出力フォーマット
連続する 1 つの整数は、Z が最長でどれくらいの期間食べ続けることができるかを示します。
Z が原点復帰できない場合は -1 を出力します。

サンプル #1
サンプル入力 #1
7 3
TTTTTTTT
TGGGGGGT
TGGGGGGT
MGGGGGGD
トゥッグッググト
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
データ 1≤N≤800,1≤S≤1000 の 100% について、マップ内の a(i,j) に M、D、および少なくとも 1 つの H が 1 つだけあることを確認します。同様に、次のことを確認します。 GからMへ行くことができる道があるはずです。

そして実際に試してみましたが、解決方法がわかりません。

私が試したこと:

BFSを試してみたのですが、初心者なのでBFSの正し方がよくわかりませんし、それが正しい考えなのかどうかもわかりません。