पैक-मैन - सुरक्षित बाहर निकलें
आप पैक-मैन गेम खेल रहे हैं। आप एक भूलभुलैया में हैं, जिसमें कुछ मॉन्स्टर भी घूम रहे हैं। आपको भूलभुलैया की बाहरी सीमा (boundary squares) में से किसी भी वर्ग तक पहुँचना है, लेकिन इस दौरान किसी भी क्षण आपका और मॉन्स्टर का स्थान एक जैसा नहीं होना चाहिए।
हर चाल में, आप एक दिशा (ऊपर, बाएँ, दाएँ या नीचे) में आगे बढ़ते हैं, और मॉन्स्टर भी किसी दिशा में आगे बढ़ते हैं।
अगर भूलभुलैया से सुरक्षित बाहर निकलना संभव है, तो आपको वह रास्ता प्रिंट करना चाहिए जो आप अपना सकते हैं। आपकी रणनीति ऐसी होनी चाहिए कि मॉन्स्टर आपकी योजना से परिचित हों, तब भी आप बाहर निकल सकें।
इनपुट (Input)
इनपुट की पहली पंक्ति में दो पूर्णांक
h और w (1 ≤ h, w ≤ 1000) दिए जाते हैं, जो भूलभुलैया की ऊँचाई और चौड़ाई दर्शाते हैं।इसके बाद की
h पंक्तियों में w अक्षर होते हैं, जो भूलभुलैया का वर्णन करते हैं:.- फ़्लोर (floor)
#- दीवार (wall)
M- मॉन्स्टर (monster)
Y- आपकी प्रारंभिक स्थिति (your initial position)
आउटपुट (Output)
आउटपुट की पहली पंक्ति में भूलभुलैया से बाहर निकलने के लिए उठाए जाने वाले क़दमों की संख्या होनी चाहिए। यदि ऐसा संभव न हो, तो
Impossible प्रिंट करें।यदि बाहर निकलना संभव है, तो अगली पंक्ति में कोई भी ऐसा मान्य पथ प्रिंट करें, जिससे आप सुरक्षित रूप से बाहर निकल सकें।
उदाहरण (Examples)
Input
5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######Output
5
RRDDRConstraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB