मेलोन रोबोट का परीक्षण करता है
Problem
मेलोन अपने नए विकास का परीक्षण करना चाहता है - एक रोबोट जो लेबिरिंथ में चल सकता है।
रोबोट n × m आकार की एक आयताकार भूलभुलैया में है। भूलभुलैया की प्रत्येक कोशिका या तो खाली है या एक बाधा द्वारा कब्जा कर लिया गया है।
रोबोट आसन्न कोशिकाओं के बीच बाईं ओर (प्रतीक "एल"), दाएं (प्रतीक "आर", ऊपर (प्रतीक "यू") या नीचे (प्रतीक "डी") के बीच जा सकता है। रोबोट केवल खाली होने पर ही सेल में जा सकता है। प्रारंभ में, रोबोट एक खाली पिंजरे में है।
मेलोन चाहता है कि रोबोट शब्दावली की दृष्टि से बिल्कुल k लंबाई के न्यूनतम चक्र से गुजरे, जो उस सेल में शुरू और समाप्त होता है जहां रोबोट शुरू में स्थित है। रोबोट को किसी भी सेल में कितनी भी बार जाने की अनुमति है (प्रारंभिक सेल सहित)।
रोबोट का मार्ग अक्षर "L", "R", "U" से मिलकर एक स्ट्रिंग द्वारा दिया गया है और "डी"। उदाहरण के लिए, यदि रोबोट पहले नीचे, फिर बाएं, फिर दाएं और ऊपर जाता है, तो उसका पथ "DLRU" लिखा जाता है।
मेलोना को यह निर्धारित करने में सहायता करें कि रोबोट का कौन सा पथ शब्दकोषीय रूप से न्यूनतम लंबाई के न्यूनतम चक्र से मेल खाता है, या मुझे बताएं कि ऐसी कोई चीज़ नहीं है।
इनपुट:
पहली पंक्ति के बाद तीन पूर्णांक n, m और k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106< / समर्थन>) — भूलभुलैया आयाम और चक्र की लंबाई।
अगली n पंक्तियों में से प्रत्येक में m वर्ण हैं — भूलभुलैया का वर्णन। यदि प्रतीक "।" है, तो वर्तमान सेल खाली है। यदि प्रतीक "*" है, तो वर्तमान सेल पर एक बाधा का कब्जा है। यदि प्रतीक "X" के बराबर है, तो शुरू में रोबोट इस सेल में है, और यह खाली है। यह गारंटी है कि चरित्र "एक्स" भूलभुलैया में ठीक एक बार होता है।
आउटपुट:
बिल्कुल k लंबाई के रोबोट का लेक्सिकोग्राफिक रूप से न्यूनतम पथ प्रिंट करें, जो उस सेल में शुरू और समाप्त होता है जहां रोबोट प्रारंभ में स्थित है। अगर ऐसा कोई रास्ता मौजूद नहीं है, तो "IMPOSSIBLE" प्रिंट करें (उद्धरण चिह्नों के बिना)।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
2 3 2
**
एक्स .. |
आरएल |
5 6 14
..***.
*...एक्स।
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*एक्स*
***
| असंभव |