로드러너 1 경비로봇 인공지능 제작

로드러너 1은 고전게임 로드러너를 넥슨에서 리메이크한 게임이다. 플레이어는 러너를 조종해서 경비로봇들을 따돌리고 맵에 뿌려진 골드를 모두 획득해 탈출하려 한다.

러너에게 가장 빨리 갈 수 있는 경로로 움직이는 경비로봇 AI를 만들어보자. 현재 게임 맵의 상태와 러너의 위치, 경비로봇의 위치가 주어졌을 때 경비로봇이 어떤 순서로 행동을 취해야 러너에게 가장 빨리 갈 수 있는지 결정하면 된다. 주어진 경비로봇의 처음 위치는 항상 블록을 밟고 서 있고, 러너는 움직이지 않는다고 가정한다.

경비로봇의 이동 규칙은 다음과 같다.

• 게임 맵은 빈 공간, 사다리, 블록으로 이뤄져 있다.
• 블록으로는 걸어들어갈 수 없다.
• 블록을 밟고 서있다면 왼쪽 혹은 오른쪽으로 이동 가능하다.
• 사다리에 매달린 상태에서는 위 혹은 아래로도 이동이 가능하다.
• 사다리는 밟고 올라설 수 있으며, 이 경우 사다리를 타고 아래로 내려갈 수 있다.
• 지금 있는 자리가 사다리에 매달리지 않고 아래가 빈 공간이라면 아래로 떨어진다.
• 왼쪽 혹은 오른쪽으로 한 칸 이동하는 데 $H$의 시간이 걸린다. (사다리를 타고 있는 중에도 왼쪽 또는 오른쪽으로 이동이 가능하고 이때도 $H$의 시간이 걸린다.)
• 사다리를 타고 위 혹은 아래로 한 칸 이동하는 데 $V$의 시간이 걸린다.
• 한 칸 아래로 떨어지는 데 F의 시간이 걸린다.

입력 형식

첫 줄에는 맵의 가로 크기 $N$과 세로 크기 $M$이 공백으로 구분되어 주어진다. $N$과 $M$은 $3\,000$ 보다 크지 않은 자연수이다. 둘째 줄에 $H$, $V$, $F$가 공백으로 구분되어 주어진다. $H$, $V$, $F$은 $10^9$ 보다 크지 않은 자연수이다. 이후 $M$개의 줄에 맵 정보가 맨 위부터 아래로 차례로 주어진다. 맵 정보는 빈 공간은 ., 블록은 B, 사다리는 H, 러너의 위치는 R, 경비로봇의 위치는 G로 주어진다.

출력 형식

첫 줄에 경비로봇이 이동할 방향을 L(왼쪽), R(오른쪽), U(위쪽), D(아래쪽)으로 공백없이 출력한다.

낙하하는 경우도 출력해야 한다. 위 상황의 경우 출력은 R, D로 출력한다. 사다리에서 오른쪽으로 이탈하는 과정이 R, 낙하가 D이다. 만약 여러 칸을 낙하하면 낙하하는 칸수만큼 D를 출력한다.

최단 시간에 러너에게 도달 가능한 경로가 여럿이라면 그 중 아무거나 하나만 출력하면 된다. 러너에게 도달 불가능할 경우 X를 출력한다.

예제

5 5
1 1 1
BBBBB
B.R.B
B.BHB
BG.HB
BBBBB

RRUUL

주의 사항

실제 게임에는 블록 파기, 매달리기 등 더 많은 요소가 있지만 이 문제에서는 다루지 않는다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설