ملون ربات را آزمایش می کند
Problem
ملون می خواهد توسعه جدید خود را آزمایش کند - روباتی که می تواند در هزارتوها حرکت کند.
ربات در یک پیچ و خم مستطیل شکل به اندازه n × m قرار دارد. هر یک از سلول های هزارتو یا خالی است یا توسط مانعی اشغال شده است.
ربات می تواند بین سلول های مجاور به سمت چپ (نماد "L")، راست (نماد "R"، بالا (نماد "U") یا پایین (نماد "D") حرکت کند. ربات تنها در صورت خالی بودن سلول می تواند به سمت سلول حرکت کند. در ابتدا، ربات در یک قفس خالی است.
ملون از ربات می‌خواهد که از نظر واژگانی حداقل چرخه طول دقیقاً k را طی کند، که در سلولی که ربات در ابتدا در آن قرار دارد شروع می‌شود و به پایان می‌رسد. ربات مجاز است هر چند بار از هر سلولی بازدید کند (از جمله سلول شروع).
مسیر ربات توسط یک رشته متشکل از کاراکترهای "L"، "R"، "U" داده می شود. و "د". به عنوان مثال، اگر ربات ابتدا به پایین، سپس چپ، سپس راست و بالا برود، سپس مسیر آن به صورت "DLRU" نوشته می شود.
به ملونا کمک کنید تعیین کند کدام مسیر ربات با حداقل چرخه واژگانی طول دقیقا k مطابقت دارد، یا به من بگویید که چنین چیزی وجود ندارد.
ورودی:
خط اول با سه عدد صحیح n، m و k دنبال می شود (1 ≤ n، m ≤ 1000، 1 ≤ k ≤ 10
6< / sup>) — ابعاد پیچ و خم و طول چرخه.
هر یک از n خط بعدی حاوی m کاراکتر — شرح هزارتو اگر نماد "." باشد، سلول فعلی خالی است. اگر نماد "*" باشد، سلول فعلی توسط یک مانع اشغال شده است. اگر نماد برابر با "X" باشد، ابتدا ربات در این سلول است و خالی است. تضمین شده است که شخصیت "X" دقیقا یک بار در پیچ و خم رخ می دهد.
خروجی:
مسیر حداقلی واژگانی ربات با طول دقیقا k را چاپ کنید، که در سلولی که ربات در ابتدا در آن قرار دارد شروع می شود و به پایان می رسد. اگر چنین مسیری وجود ندارد، "غیر ممکن" را چاپ کنید (بدون نقل قول).
مثال:
<بدن>
| ورودی |
خروجی |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
غیر ممکن |