돌 밀기

$2$차원 격자판 모양의 맵이 있다. 맵의 일부 칸들에는 장애물이 있고, 또한 큰 돌 하나가 있는데 이 돌은 $2\times 2$칸을 차지한다. 한 사람이 힘을 내어 이 돌을 시작 위치에서 목적지 위치로 옮기려고 한다. 아래 그림에서 짙은 남색 칸은 장애물이며, 돌과 사람이 표시되어 있고, 회색으로 표시된 부분은 목표 지점이다. 사람은 돌을 “밀기만” 할 수 있고, 상하좌우로 한 칸씩 움직일 수 있다.

위 그림에서 사람이 왼쪽으로 한 칸 움직이면 돌을 왼쪽으로 한 칸 밀게 된다. 그리고 사람이나 돌은 모두 장애물과 겹칠 수 없고 사람과 돌도 겹칠 수 없다. 돌이 차지한 $4$개의 칸에 사람이 상하 혹은 좌우로 인접한 경우에만 돌을 밀 수 있다. 그 경우, 돌이 차지한 칸으로 사람이 한 칸 움직이면 돌도 밀려서 같은 방향으로 한 칸 움직인다. 돌과 장애물이 겹칠 수 없다는 점을 생각하면 돌이 밀려가야 하는 두 칸 중 하나에라도 장애물이 있으면 이렇게 미는 것이 불가능함을 알 수 있다. (문제에 제공되는 시뮬레이터의 내용을 참고하면 좋다.)

돌을 목적지까지 옮기기 위해 사람이 움직여야 하는 이동 커맨드를 구하자. 이때 사람이나 돌의 이동 횟수가 최소일 필요는 없다.

입력 형식

첫째 줄에 격자 칸의 행 개수 $N$과 열 개수 $M$이 주어진다. ($7 \le N, M \le 27$)

다음 $N$개의 줄에 격자 칸의 상황이 한 행씩 길이 $M$인 문자열로 주어진다. 각 칸에 해당하는 글자가 .(점)이면 빈칸, X(대문자 엑스)이면 장애물이라는 뜻이다. 그리고 글자가 *(별)이면 돌이 있다는 뜻이다. 돌이 차지하는 $2\times 2$칸에 모두 *이 주어진다. 또한 글자가 -(마이너스)이면 목표 지점이라는 뜻이다. 목표 지점이 차지하는 $2\times 2$칸에 모두 -가 주어진다. 글자가 O(대문자 오)이면 사람이 있다는 뜻이다. 격자 칸의 테두리에 해당하는 칸에는 모두 장애물이 있다.

출력 형식

사람이 움직이는 과정을 나타내는 이동 커맨드를 출력한다. 사람이 왼쪽으로 한 칸 움직이면 L, 오른쪽으로 한 칸 움직이면 R, 위로 한 칸 움직이면 U, 아래로 한 칸 움직이면 D로, 움직인 순서에 따라 하나의 문자열로 만들어 출력한다. 단, 출력하는 이동 커맨드의 길이가 $100\,000$을 넘으면 안 된다.

예제

7 7
XXXXXXX
X...O.X
X...X
X...X
X.--..X
X.--..X
XXXXXXX

LDD

채점 방식

이 문제는 풀이 소스코드를 제출하지 않고, 각 테스트케이스의 입력데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

해설