आपकी कृपा तथा धन्यवाद! इस प्रश्न को कैसे हल करें? (सी++)

नमस्कार पेशेवरों, दैनिक अभ्यास के दौरान मुझे इस प्रश्न का सामना करना पड़ा:

उद्धरण:

सेलिब्रिटी जेड के साथ परेशानी
विवरण
सेलेब्रिटी Z बहुत लो प्रोफाइल है। Z और Y अपने रात्रिभोज पर ध्यान केंद्रित कर रहे हैं। उन्हें अभी ताज़ा ख़बर मिल ही रही थी कि कुछ पपराज़ी टीमें यहां उमड़ रही हैं।
लिटिल ज़ेड वास्तव में यह नहीं समझता है कि ये लोग आजकल गपशप के इतने भूखे कैसे हैं, लेकिन आज, लिटिल ज़ेड वास्तव में अपना स्वादिष्ट भोजन छोड़ना नहीं चाहता है, इसलिए वह केवल खाने के लिए यथासंभव लंबे समय तक रह सकता है, और वह उम्मीद करता है कि जब तक संभव हो सके पापराज़ी की नजरों से बचकर खाएं।
जिस शहर में लिटिल ज़ेड खाता है उसे एन पंक्तियों और एन स्तंभों के साथ एक वर्गाकार जाली के रूप में देखा जा सकता है, और प्रत्येक जाली निम्नलिखित मामलों के साथ ए (आई, जे) प्रकार की है:
1. टी, यह दर्शाता है कि यह जाली एक निजी आवासीय भवन है
2. जी, यह दर्शाता है कि यह ग्रिड एक खाली जगह है
3. एम, जिसका अर्थ है कि यह जाली वह स्थान है जहां छोटा ज़ेड खा रहा है, लेकिन निश्चित रूप से इसे एक खाली जगह या सार्वजनिक (गैर-निजी) इमारत के रूप में भी देखा जा सकता है
4. D, दर्शाता है कि यह वर्ग Z का घर है।
5. एच, जिसका अर्थ है कि यह सेल पापराज़ी का अड्डा है।
हम दो ग्रिडों को आसन्न मानते हैं यदि उनके किनारे समान हों, यानी, ऊपर, नीचे, बाएँ और दाएँ ग्रिड आसन्न हों।
जब भी लिटिल ज़ेड और पापराज़ी चलेंगे, वे केवल निकटवर्ती चौराहों पर चलेंगे, और उनमें से कोई भी अन्य लोगों की निजी इमारतों में नहीं घुसेगा। लिटिल ज़ेड प्रति सेकंड अधिकतम एस कदम उठाता है, और चूंकि लिटिल ज़ेड के पास एक पेशेवर रेस कार ड्राइवर है, लिटिल डब्ल्यू, एक विशेष ड्राइवर के रूप में, एस का मूल्य बहुत बड़ा हो सकता है।
जब लिटिल ज़ेड को उनके आगमन के बारे में पता चला तो पापराज़ी अपने अड्डे में थे। जैसे-जैसे समय बीतता है, हर सेकंड निम्नलिखित क्रम में कई घटनाएँ घटित होती हैं:
1. यदि लिटिल ज़ेड अभी भी खाने की जगह पर है, तो वह अभी खाना चुन सकता है, या भागना शुरू कर सकता है
* यदि खाना जारी रखना है, तो लिटिल ज़ेड इस सेकंड में नहीं हिलेगा, और यदि भाग जाना है, तो लिटिल ज़ेड अगले कुछ सेकंड में शहर के चारों ओर एस कदम से अधिक नहीं चल सकता है। एक बार जब यह निकल जाएगा, तो लिटिल ज़ेड बिना रुके भागता रहेगा। यदि यह किसी निश्चित स्थान पर पपराज़ो से मिलता है, तो लिटिल ज़ेड को पकड़ लिया जाएगा। 2.
2. जब Z खाना जारी रखने या हिलने-डुलने का विकल्प चुनता है, तो सभी पपराज़ी ग्रिड के चारों ओर एक कदम आगे बढ़ जाएंगे, और एक बार जब पपराज़ी ग्रिड पर पहुंच जाएंगे, तो एक पपराज़ी को वहां रहने के लिए भेजा जाएगा। शुरुआत में, पापराज़ी उस ग्रिड पर कब्ज़ा कर लेते हैं जहाँ सभी पापराज़ी के अड्डे स्थित हैं।
* उदाहरण के लिए, यदि लिटिल ज़ेड पहले सेकंड में जहां है वहीं रहना चुनता है, तो पपराज़ी पहले सेकंड में सभी दिशाओं में फैल जाएंगे, और यदि वे लिटिल ज़ेड के सामने आते हैं, तो लिटिल ज़ेड तस्वीर में कैद हो जाएगा।
* यदि छोटा Z (1,1) से शुरू होता है, S 2 है, और पहले सेकंड में आगे बढ़ना चुनता है, तो छोटा Z पहले सेकंड में (1,2),(1,3) जाली पर जा सकता है। यह मानते हुए कि पापराज़ी पहले सेकंड में (1,2) जाली पर आ सकता है, तो छोटा Z भी उस समय (1,2) जाली से गुजर सकता है, क्योंकि छोटे Z के रुकने या स्थानांतरित होने के बाद पापराज़ी फैल जाता है, और छोटा Z पहले सेकंड के अंत तक (1,3) जाली तक जा सकता है। 1 सेकंड के अंत में, और पापराज़ी का सामना नहीं होगा; यदि पापराज़ी 1 सेकंड के अंत में (1,3) जाली पर आ सकता है, तो लिटिल ज़ेड ((1,3) जाली पर नहीं जा सकता।
* दूसरे शब्दों में, लिटिल ज़ेड के रुकने या स्थानांतरित होने का निर्णय लेने के बाद पपराज़ी हमेशा अलग हो जाते हैं, और लिटिल ज़ेड हर सेकंड एक ऐसी स्थिति में रहता है, अगर वह घर पर नहीं है, तो यह सुनिश्चित करता है कि पपराज़ी इस सेकंड उस स्थिति में नहीं हो सकता है।
न तो पापराज़ी और न ही लिटिल ज़ेड शहर के किनारे से आगे जा सकते हैं, और पापराज़ी लिटिल ज़ेड के घर पर कब्ज़ा नहीं कर सकते हैं। अब लिटिल ज़ेड जानना चाहता है कि अगर उसे सुरक्षित घर लौटना है तो वह अधिकतम कितने समय तक खाना खा सकता है।
“समस्या समाधानकर्ता से कुछ प्रकार के संकेत
1. न तो लिटिल ज़ेड और न ही पापराज़ी मानचित्र के टी-ग्रिड तक चल सकते हैं, लेकिन वे दोनों एम-ग्रिड तक चल सकते हैं। 2.
2. उदाहरण का अनुसरण करते हुए प्रश्न को ध्यानपूर्वक पढ़ें।

इनपुट प्रारूप
पहली पंक्ति में दो पूर्णांक, N और S हैं, जो शहर के आकार और लिटिल Z द्वारा प्रति सेकंड तय की जा सकने वाली अधिकतम दूरी को दर्शाते हैं।
अगली N पंक्तियाँ N वर्णों से बनी हैं, जहाँ a(i,j) i-वीं पंक्ति के jवें कॉलम की विशिष्ट स्थिति को दर्शाता है। a(i,j) 5 प्रकार के वर्णों T, G, M, D, और H में से एक है। a(i,j) के अर्थ के लिए शीर्षक देखें।

आउटपुट स्वरूप
एक पंक्ति में एक पूर्णांक, यह दर्शाता है कि Z अधिकतम कितनी देर तक खाना जारी रख सकता है।
यदि Z के लिए घर लौटना असंभव है, तो आउटपुट -1।

नमूना #1
नमूना इनपुट #1
7 3
टीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटीटी
टीजीजीजीजीजीटी
टीजीजीजीजीजीटी
एमजीजीजीजीजीडी
टीजीजीजीजीटी
टीजीजीजीजीजीटी
टीजीएचएचजीजीटी

नमूना आउटपुट #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 तक जा सके।

और मैंने वास्तव में कोशिश की लेकिन मुझे नहीं पता कि इसे कैसे हल किया जाए।

मैंने क्या प्रयास किया है:

मैंने बीएफएस की कोशिश की है, लेकिन चूंकि मैं एक नौसिखिया हूं तो मैं वास्तव में नहीं जानता कि बीएफएस को सही तरीके से कैसे ठीक किया जाए, और मुझे यह भी यकीन नहीं है कि यह एक सही विचार है या नहीं।