من فضلك و شكرا لك! كيفية حل هذا السؤال؟ (ج++)

مرحبًا أيها المحترفون، لقد واجهت هذا السؤال أثناء التدريب اليومي:

يقتبس:

المشكلة مع المشاهير Z
وصف
المشاهير Z شخصية منخفضة للغاية. يركز Z وY على العشاء. لقد كانوا يتلقون للتو آخر الأخبار التي تفيد بأن بعض فرق المصورين يحتشدون هنا.
لا يفهم Little Z حقًا مدى جوع هؤلاء الأشخاص للنميمة هذه الأيام، ولكن اليوم، Little Z لا يريد حقًا التخلي عن وجبته اللذيذة، لذلك يمكنه البقاء فقط لأطول فترة ممكنة لتناول الطعام، ويأمل في ذلك تناول الطعام لأطول فترة ممكنة دون أن يقبض عليك المصورون.
يمكن النظر إلى المدينة التي يأكل فيها Little Z على أنها شبكة مربعة بها عدد N من الصفوف وN من الأعمدة، وكل شبكة من النوع a(i,j) في الحالات التالية:
1. T مما يدل على أن هذه الشبكة عبارة عن مبنى سكني خاص
2.G، تشير إلى أن هذه الشبكة عبارة عن قطعة أرض فارغة
3. M، مما يعني أن هذه الشبكة هي المكان الذي يأكل فيه Z الصغير، ولكن بالطبع يمكن أيضًا اعتبارها قطعة أرض خالية أو مبنى عام (غير خاص)
4. يشير D إلى أن هذا المربع هو منزل Z.
5.H، مما يعني أن هذه الخلية هي وكر المصورين.
نحن نعتبر الشبكتين متجاورتين إذا كانت لهما نفس الحواف، أي أن الشبكات العلوية والسفلية واليسرى واليمنى متجاورة.
عندما يسير Little Z والمصورون، فسوف يسيرون فقط في المربعات المجاورة، ولن يقتحم أي منهم المباني الخاصة للآخرين. يأخذ Little Z خطوات S على الأكثر في الثانية، وبما أن Little Z لديه سائق سيارات سباق محترف، Little W، كسائق خاص، فإن قيمة S يمكن أن تكون كبيرة جدًا.
كان المصورون في أوكارهم عندما علم Little Z بوصولهم. ومع مرور الوقت، تحدث عدة أحداث في كل ثانية بالترتيب التالي:
1. إذا كان Little Z لا يزال في مكان تناول الطعام، فيمكنه اختيار تناول الطعام الآن في هذه اللحظة، أو البدء في الهروب
* إذا كان سيستمر في تناول الطعام، فلن يتحرك Little Z في هذه الثانية، وإذا كان سيهرب بعيدًا، فلن يتمكن Little Z من التحرك أكثر من خطوة S حول المدينة في الثواني القليلة التالية. بمجرد مغادرته، سيستمر Little Z في الهروب دون توقف. إذا التقى بمصور مصور في مكان معين، فسيتم القبض على Little Z. 2.
2. عندما يختار Z الاستمرار في تناول الطعام أو التحرك، سيتحرك جميع المصورين خطوة واحدة للأمام حول الشبكة، وبمجرد وصول المصورين إلى الشبكة، سيتم إرسال المصورين للبقاء هناك. في البداية، يحتل المصورون الشبكة التي توجد بها جميع أوكار المصورين.
* على سبيل المثال، إذا اختار Little Z البقاء حيث هو في الثانية الأولى، فسوف ينتشر المصورون في كل الاتجاهات في الثانية الأولى، وإذا صادفوا Little Z، فسيتم القبض على Little Z في الصورة
* إذا بدأ Z الصغير عند (1,1)، وS هو 2، واختار التحرك في الثانية الأولى، فيمكن لـ Z الصغير الانتقال إلى الشبكة (1,2)، (1,3) في الثانية الأولى. بافتراض أن المصورين يمكنهم الوصول إلى الشبكة (1,2) في الثانية الأولى، فيمكن أيضًا أن يمر Z الصغير عبر الشبكة (1,2) في ذلك الوقت، لأن المصورين ينتشرون بعد أن يختار Z الصغير البقاء أو التحرك، ويمكن أن ينتقل Z الصغير إلى الشبكة (1،3) بنهاية الثانية الأولى. في نهاية ثانية واحدة، ولن يواجه المصورين؛ إذا تمكن المصورون من الوصول إلى الشبكة (1,3) في نهاية ثانية واحدة، فلن يتمكن Little Z من الوصول إلى الشبكة ((1,3).
* بمعنى آخر، ينتشر المصورون دائمًا بعد أن يقرر Little Z البقاء أو التحرك، ويكون Little Z في وضع كل ثانية، إذا لم يكن في المنزل، يضمن أن المصورين لا يمكن أن يكونوا في هذا الوضع في هذه الثانية.
لا يستطيع المصورون ولا Little Z تجاوز حافة المدينة، ولا يستطيع المصورون الاستيلاء على منزل Little Z. يريد Little Z الآن معرفة الحد الأقصى للوقت الذي يمكنه الاستمرار في تناول الطعام فيه إذا كان عليه أن يتمكن من العودة إلى المنزل بأمان.
“بعض التلميحات اللطيفة من حل المشكلات
1. لا يستطيع Little Z ولا المصورون المشي إلى شبكة T الخاصة بالخريطة، لكن يمكنهم السير إلى شبكة M. 2.
2. اقرأ السؤال بعناية، متبعًا المثال.

نمط الإدخال
يحتوي السطر الأول على عددين صحيحين، N وS، يمثلان حجم المدينة والحد الأقصى للمسافة التي يمكن أن يتحركها Little Z في الثانية.
يتكون كل من صفوف N التالية من أحرف N، حيث تشير a(i,j) إلى الوضع المحدد للعمود j في الصف i. a(i,j) هو أحد أنواع الأحرف الخمسة T وG وM وD وH. راجع العنوان للتعرف على معنى a(i,j).

تنسيق الإخراج
عدد صحيح واحد على التوالي، يشير إلى المدة التي يمكن أن يستمر فيها Z في تناول الطعام على الأكثر.
إذا كان من المستحيل على Z العودة إلى المنزل، فسيتم إخراج -1.

العينة رقم 1
نموذج الإدخال رقم 1
7 3
تتتتتتتتت
تجججججت
تجججججت
مجججججد
تججججت
تجججججت
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) في الخريطة يحتوي على M واحد فقط وD واحد وH واحد على الأقل. وبالمثل، تأكد من أن يجب أن يكون هناك مسار يمكن أن ينتقل من G إلى M.

ولقد حاولت حقًا ولكن لا أعرف كيفية حلها.

ما حاولت:

لقد جربت BFS، لكن بما أنني مبتدئ، لا أعرف حقًا كيفية تصحيح BFS، ولست متأكدًا أيضًا مما إذا كانت هذه فكرة صحيحة أم لا.