Problem
Melone, labirentlerde hareket edebilen yeni robotunu test etmek istiyor.
Robot, n times;m boyutunda dikdörtgen bir labirentin içindedir. Labirentin her hücresi ya boştur ya da bir engel tarafından işgal edilmiştir.
Robot bitişik hücreler arasında sola ("L" sembolü), sağa ("R" sembolü), yukarı ("U" sembolü) veya aşağı ("D" sembolü) yönünde hareket edebilir. Robot, yalnızca boşsa bir hücreye hareket edebilir. Başlangıçta robot boş bir kafestedir.
Melone, robotun, robotun başlangıçta bulunduğu hücrede başlayan ve biten tam olarak k uzunluğundaki sözlüksel olarak minimum döngüden geçmesini istiyor. Robotun herhangi bir hücreyi herhangi bir sayıda ziyaret etmesine izin verilir (başlangıç hücresi dahil).
Robotun yolu, "L", "R", "U" karakterlerinden oluşan bir dizi ile verilir. ve "D". Örneğin robot önce aşağı, sonra sola, sonra sağa ve yukarı gidiyorsa yolu "DLRU" olarak yazılır.
Melona'nın robotun hangi yolunun tam olarak k uzunluğundaki sözlüksel olarak minimum döngüye karşılık geldiğini belirlemesine yardım edin veya bana böyle bir şeyin olmadığını söyleyin.
Giriş:
İlk satırı üç tamsayı takip eder n, m ve k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6<) / destek>) — labirent boyutları ve döngü uzunluğu.
Sonraki n satırın her biri m karakter içerir — labirentin tanımı. Sembol "." ise, geçerli hücre boştur. Sembol "*" ise, geçerli hücre bir engelle dolu demektir. Sembol "X" e eşitse, başlangıçta robot bu hücrededir ve boştur. "X" karakterinin garanti edilir labirentte tam olarak bir kez gerçekleşir.
Çıktı:
Robotun başlangıçta bulunduğu hücrede başlayan ve biten tam olarak k uzunluğundaki Robotun sözlükbilimsel olarak minimum yolunu yazdırın. Böyle bir yol yoksa, "İMKANSIZ" yazdırın (tırnak işaretleri olmadan).
Örnekler:
| Giriş |
Çıktı |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLRRRUURU |
3 3 4
***
*X*
*** |
İMKANSIZ |