Silahkan dan terima kasih! Bagaimana cara mengatasi pertanyaan ini? (C++)

Halo para profesional, saya menemui pertanyaan ini selama latihan sehari-hari:

Mengutip:

Masalah dengan Selebriti Z
Keterangan
Selebriti Z sangat low profile. Z dan Y sedang berkonsentrasi pada makan malam mereka. Mereka baru saja mendapat kabar terbaru bahwa beberapa tim paparazzi berkerumun di sini.
Little Z benar-benar tidak mengerti bagaimana orang-orang ini begitu haus akan gosip saat ini, tapi hari ini, Little Z benar-benar tidak mau melepaskan makanan lezatnya, jadi dia hanya bisa tinggal selama mungkin untuk makan, dan dia berharap untuk melakukannya. makan selama mungkin tanpa ketahuan paparazzi.
Kota tempat Little Z makan dapat dilihat sebagai kisi persegi dengan N baris dan N kolom, dan setiap kisi bertipe a(i,j) dengan kasus berikut:
1. T, menunjukkan bahwa kisi-kisi ini merupakan bangunan tempat tinggal pribadi
2. G, menandakan bahwa grid ini merupakan lahan kosong
3. M, artinya kisi-kisi ini adalah tempat makan si kecil Z, namun tentunya bisa juga dilihat sebagai tanah kosong atau bangunan umum (bukan milik pribadi).
4. D, menandakan bahwa persegi ini adalah rumah Z.
5. H yang artinya sel ini adalah sarang paparazzi.
Kita menganggap dua grid bertetangga jika keduanya mempunyai tepi yang sama, yaitu grid atas, bawah, kiri, dan kanan berdekatan.
Setiap kali Little Z dan paparazzi berjalan, mereka hanya akan berjalan di alun-alun yang berdekatan, dan tidak satupun dari mereka akan masuk ke gedung pribadi orang lain. Little Z mengambil langkah paling banyak S per detik, dan karena Little Z memiliki pengemudi mobil balap profesional, Little W, sebagai pengemudi khusus, nilai S bisa sangat besar.
Paparazzi berada di sarangnya saat Little Z mengetahui kedatangan mereka. Seiring berjalannya waktu, setiap detik sejumlah peristiwa terjadi dengan urutan sebagai berikut:
1. jika Little Z masih berada di tempat makan, maka dia dapat memilih untuk makan sekarang juga, atau mulai melarikan diri
* Jika ingin terus makan, maka Little Z tidak akan bergerak pada detik ini, dan jika ingin melarikan diri, maka Little Z tidak dapat bergerak lebih dari S langkah mengelilingi kota dalam beberapa detik berikutnya. Begitu ia pergi, Little Z akan terus kabur tanpa henti. Jika bertemu paparazzo di lokasi tertentu, maka Little Z akan ditangkap. 2.
2. Ketika Z memilih untuk terus makan atau bergerak, semua paparazzi akan bergerak satu langkah lebih jauh di sekitar grid, dan setelah paparazzi mencapai grid, paparazzo akan dikirim untuk tetap di sana. Pada awalnya, paparazzi menempati jaringan tempat semua sarang paparazzi berada.
* Misalnya, jika Little Z memilih untuk tetap di tempatnya pada detik pertama, paparazzi akan menyebar ke segala arah pada detik pertama, dan jika mereka menemukan Little Z, Little Z akan tertangkap dalam gambar
* Jika Z kecil dimulai pada (1,1), S adalah 2, dan memilih berpindah pada detik pertama, maka Z kecil dapat berpindah ke kisi (1,2),(1,3) pada detik pertama. Dengan asumsi paparazzi dapat sampai ke kisi (1,2) pada detik pertama, maka Z kecil juga dapat melewati kisi (1,2) pada saat itu, karena paparazzi menyebar setelah Z kecil memilih diam atau pindah, dan Z kecil dapat mencapai kisi (1,3) pada akhir detik pertama. di akhir 1 detik, dan tidak akan bertemu paparazzi; jika paparazzi dapat mencapai kisi (1,3) pada akhir 1 detik, maka Z Kecil tidak dapat mencapai kisi ((1,3).
* Dengan kata lain, paparazzi selalu menyebar setelah Little Z memutuskan untuk tetap tinggal atau pindah, dan Little Z setiap detik berada dalam posisi yang jika tidak ada di rumah, memastikan paparazzi tidak dapat berada di posisi tersebut detik ini.
Baik paparazzi maupun Little Z tidak dapat melampaui pinggiran kota, dan paparazzi tidak dapat mengambil alih rumah Little Z. Kini Little Z ingin tahu berapa lama waktu maksimal dia bisa terus makan jika harus bisa pulang ke rumah dengan selamat.
“Beberapa Petunjuk Baik dari Pemecah Masalah
1. Baik Little Z maupun paparazzi tidak bisa berjalan ke jaringan-T di peta, tapi mereka berdua bisa berjalan ke jaringan-M. 2.
2. Bacalah soal dengan cermat, ikuti contohnya.

Masukkan format
Baris pertama berisi dua bilangan bulat, N dan S, yang mewakili ukuran kota dan jarak maksimum yang dapat ditempuh Little Z per detik.
N baris berikutnya masing-masing terdiri dari N karakter, dengan a(i,j) menunjukkan situasi spesifik kolom ke-j dari baris ke-i. a(i,j) merupakan salah satu dari 5 macam karakter T, G, M, D, dan H. Lihat judulnya untuk mengetahui arti a(i,j).

Format output
Satu bilangan bulat berturut-turut, menunjukkan berapa lama Z dapat terus makan paling lama.
Jika Z tidak mungkin kembali ke rumah, maka output -1.

Contoh #1
Contoh Masukan #1
7 3
TTTTTTTTT
TGGGGGGGT
TGGGGGGGT
MGGGGGGD
TGGGGGT
TGGGGGGGT
TGHHGGGT

Contoh Keluaran #1
2

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

Untuk 30% data, S=1.
Untuk 50% data, N≤60
Untuk 100% data 1≤N≤800,1≤S≤1000, dan pastikan bahwa a(i,j) pada peta hanya memiliki satu M, satu D, dan setidaknya satu H. Demikian pula, pastikan bahwa pasti ada jalan yang bisa ditempuh dari G ke M.

Dan saya benar-benar mencoba tetapi tidak tahu bagaimana cara mengatasinya.

Apa yang saya coba:

Saya sudah mencoba BFS, namun berhubung saya masih pemula, saya tidak terlalu tahu cara memperbaiki BFS yang benar, dan saya juga tidak yakin apakah itu pemikiran yang benar atau tidak.