अविराम रोबोट
कुछ विद्यार्थी एक ऐसा रोबोट विकसित कर रहे थे जो भूलभुलैया (maze) में चल सकता है। लेकिन यह रोबोट अभी पूर्णरूप से सक्षम नहीं है क्योंकि यह तब तक अपनी दिशा नहीं बदल सकता या रुक नहीं सकता, जब तक कि वह किसी दीवार या अवरोध से न टकरा जाए। इसी वजह से, जब यह चलना शुरू करता है, तो उसे अपनी मौजूदा दिशा में निकटतम दीवार तक जाना ही होगा, और उसके बाद ही वह नई दिशा चुन सकता है।
आपको यह निर्धारित करना है कि रोबोट को शुरुआती बिंदु
S से अंतिम बिंदु E तक पहुँचने के लिए न्यूनतम कितनी चालों (moves) की आवश्यकता होगी, और उन कमांडों को प्रिंट करना होगा जो विद्यार्थी इस रोबोट को भेजेंगे ताकि वह लक्ष्य तक पहुँच सके:- L - move left
- U - move up
- R - move right
- D - move down
इनपुट
इनपुट की पहली पंक्ति में दो संख्याएँ
h और w (2 ≤ h, w ≤ 100) दी जाती हैं, जो ग्रिड की ऊँचाई (height) और चौड़ाई (width) को दर्शाती हैं।अगली
h पंक्तियों में w वर्ण होते हैं, जो ग्रिड का प्रतिनिधित्व करते हैं:.फर्श
#दीवार
Sप्रारंभिक बिंदु
Eअंतिम बिंदु
यह सुनिश्चित किया गया है कि ग्रिड चारों तरफ से दीवारों से घिरा हुआ है, ताकि रोबोट इसके बाहर न जा पाए।
आउटपुट
प्रोग्राम को पहली पंक्ति में शुरुआती स्थिति से अंतिम स्थिति तक पहुँचने के लिए आवश्यक न्यूनतम चालों की संख्या प्रिंट करनी चाहिए। दूसरी पंक्ति में उन सभी कमांडों को प्रिंट करें जो विद्यार्थियों को रोबोट को भेजनी होंगी। यदि एक से अधिक उत्तर संभव हैं, तो कोई भी मान्य उत्तर प्रदर्शित किया जा सकता है।
यदि रोबोट के लिए अंतिम बिंदु तक पहुँचना असंभव हो, तो प्रोग्राम को
Impossible प्रिंट करना चाहिए।उदाहरण
Input
7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########Output
4
RDLUसंकेत (Hint)
आप प्रारंभिक बिंदु को फर्श (
.) और अंतिम बिंदु को दीवार (#) की तरह मानकर चल सकते हैं।Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB