Problem
Melone은 미로를 통해 이동할 수 있는 로봇인 그의 새로운 개발을 테스트하고 싶어합니다.
로봇은 n××m 크기의 직사각형 미로에 있습니다. 미로의 각 셀은 비어 있거나 장애물로 가득 차 있습니다.
로봇은 인접한 셀 사이를 왼쪽(기호 "L"), 오른쪽(기호 "R", 위(기호 "U") 또는 아래(기호 "D")로 이동할 수 있습니다. 로봇은 셀이 비어 있는 경우에만 셀로 이동할 수 있습니다. 처음에 로봇은 빈 케이지에 있습니다.
Melone은 로봇이 처음에 로봇이 위치한 셀에서 시작하고 끝나는 길이 k의 사전식 최소 주기를 로봇이 통과하기를 원합니다. 로봇은 모든 셀을 여러 번 방문할 수 있습니다(시작 셀 포함).
로봇의 경로는 문자 "L", "R", "U"로 구성된 문자열로 제공됩니다. 그리고 "D". 예를 들어 로봇이 먼저 아래로 이동한 다음 왼쪽으로 이동한 다음 오른쪽 위로 이동하면 경로가 "DLRU"로 기록됩니다.
Melona가 로봇의 어떤 경로가 사전학적으로 최소 주기 길이인 k에 해당하는지 결정하도록 도와주거나 그런 것이 없다고 말해주세요.
입력:
첫 번째 줄 다음에는 세 개의 정수 n, m 및 k가 옵니다(1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< / sup>) — 미로 치수 및 사이클 길이.
다음 n행 각각에는 m개의 문자가 포함됩니다. — 미로에 대한 설명. 기호가 "."이면 현재 셀이 비어 있는 것입니다. 기호가 "*"이면 현재 셀에 장애물이 있는 것입니다. 기호가 "X"와 같으면 처음에 로봇이 이 셀에 있고 비어 있습니다. 문자 "X"가 보장됩니다. 미로에서 정확히 한 번 발생합니다.
출력:
길이가 정확히 k인 로봇의 사전식 최소 경로를 인쇄합니다. 이 경로는 로봇이 처음 위치한 셀에서 시작하고 끝납니다. 그러한 경로가 존재하지 않으면 "IMPOSSIBLE"을 인쇄하십시오. (따옴표 제외).
예:
<몸>
| 입력 |
출력 |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLLRRRUURU |
3 3 4
***
*엑스*
*** |
불가능 |