Problem
Melone muốn thử nghiệm sự phát triển mới của mình - một robot có thể di chuyển trong mê cung.
Rô-bốt đang ở trong một mê cung hình chữ nhật có kích thước n &lần; m. Mỗi ô của mê cung đều trống hoặc có chướng ngại vật chiếm giữ.
Robot có thể di chuyển giữa các ô liền kề sang trái (ký hiệu "L"), phải (ký hiệu "R", lên (ký hiệu "U") hoặc xuống (ký hiệu "D"). Robot chỉ có thể di chuyển đến một ô nếu nó trống. Ban đầu, robot ở trong một cái lồng trống.
Melone muốn rô-bốt đi qua chu kỳ có độ dài chính xác là tối thiểu theo từ điển học, bắt đầu và kết thúc tại ô nơi rô-bốt được đặt ban đầu. Robot được phép truy cập bất kỳ ô nào với số lần bất kỳ (kể cả ô bắt đầu).
Đường đi của robot được cho bởi một chuỗi gồm các ký tự "L", "R", "U" và "D". Ví dụ: nếu rô-bốt đi xuống trước, sau đó sang trái, rồi sang phải và đi lên, thì đường đi của rô-bốt được viết là "DLRU".
Hãy giúp Melona xác định đường đi của rô-bốt tương ứng với chu kỳ có độ dài chính xác k theo từ điển học hoặc cho tôi biết là không có điều đó.
Đầu vào:
Theo sau dòng đầu tiên là ba số nguyên n, m và k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< /sup>) — kích thước mê cung và độ dài chu kỳ.
Mỗi dòng trong số n dòng tiếp theo chứa m ký tự — miêu tả mê cung. Nếu ký hiệu là ".", thì ô hiện tại trống. Nếu ký hiệu là "*", thì ô hiện tại đang bị vật cản chiếm giữ. Nếu ký hiệu bằng "X", thì ban đầu robot ở trong ô này và nó trống. Đảm bảo rằng ký tự "X" xảy ra đúng một lần trong mê cung.
Đầu ra:
In ra đường đi tối thiểu theo từ điển của Robot có độ dài chính xác k, bắt đầu và kết thúc tại ô nơi Robot được đặt ban đầu. Nếu không có đường dẫn như vậy tồn tại, hãy in "IMPOSSIBLE" (không có dấu ngoặc kép).
Ví dụ:
| Đầu vào |
Đầu ra |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
KHÔNG THỂ |