البطيخ يختبر الروبوت
Problem
يريد Melone اختبار تطوره الجديد - روبوت يمكنه التحرك عبر المتاهات.
الروبوت في متاهة مستطيلة بحجم n & thinsp؛ & times؛ & thinsp؛ m. كل خلية من خلايا المتاهة إما فارغة أو مشغولة بعائق. & nbsp ؛
يمكن للروبوت أن يتحرك بين الخلايا المتجاورة إلى اليسار (الرمز "L") أو اليمين (الرمز "R" أو الأعلى (الرمز "U") أو الأسفل (الرمز "D"). يمكن للروبوت أن ينتقل إلى خلية فقط إذا كانت فارغة. في البداية ، الروبوت في قفص فارغ.
يريد Melone أن يمر الروبوت عبر الحد الأدنى لدورة الطول المعجمية بالضبط k ، والتي تبدأ وتنتهي في الخلية حيث يوجد الروبوت في البداية. يُسمح للروبوت بزيارة أي خلية بأي عدد من المرات (بما في ذلك خلية البداية).
يتم تحديد مسار الروبوت من خلال سلسلة تتكون من الأحرف "L" و "R" و "U" و "د". على سبيل المثال ، إذا هبط الروبوت أولاً ، ثم يسارًا ثم يمينًا ثم لأعلى ، فسيتم كتابة مساره كـ "DLRU".
ساعد Melona في تحديد مسار الروبوت الذي يتوافق مع الحد الأدنى لدورة الطول المعجمي بالضبط k ، أو أخبرني أنه لا يوجد شيء من هذا القبيل.
الإدخال:
السطر الأول متبوع بثلاثة أعداد صحيحة n و m و k (1 & thinsp؛ & le؛ & thinsp؛ n، & thinsp؛ m & thinsp؛ & le؛ & thinsp؛ 1000، 1 & thinsp؛ & le؛ & thinsp؛ k & thinsp؛ & le؛ & thinsp؛ 10 6 < / سوب>) و [مدش] ؛ أبعاد المتاهة وطول الدورة.
يحتوي كل سطر من الأسطر n التالية على أحرف m & [مدش] ؛ وصف المتاهة. إذا كان الرمز "." ، تكون الخلية الحالية فارغة. إذا كان الرمز "*" ، فإن الخلية الحالية تحتلها عائق. إذا كان الرمز يساوي "X" ، يكون الروبوت في هذه الخلية مبدئيًا ، ويكون فارغًا. نضمن أن الحرف "X" يحدث مرة واحدة بالضبط في المتاهة.
الإخراج:
اطبع المسار الأدنى المعجمي للروبوت الذي يبلغ طوله k بالضبط ، والذي يبدأ وينتهي في الخلية حيث يوجد الروبوت في البداية. في حالة عدم وجود مثل هذا المسار ، اطبع "مستحيل" (بدون اقتباسات).
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
2 3 2
. **
X .. |
RL |
5 6 14
.. ***.
* ... X.
.. * ...
.. *. **
.... *. |
DLDDLLLRRRUURU |
3 3 4
***
* X *
*** |
مستحيل
|