Kaeru Jump
면접 대비시간 제한8초메모리 제한512 MB
최대 30개의 잎이 있는 격자에서 개구리가 앞, 왼쪽, 오른쪽 중 한 방향으로 가장 가까운 잎으로 점프하고 떠난 잎은 가라앉을 때, 잎 하나만 남기는 이동 순서를 찾는다.
문제
There is a frog living in a big pond. He loves jumping between lotus leaves floating on the pond. Interestingly, these leaves have strange habits. First, a leaf will sink into the water after the frog jumps from it. Second, they are aligned regularly as if they are placed on the grid points as in the example below.
Figure 1: Example of floating leaves
Recently, He came up with a puzzle game using these habits. At the beginning of the game, he is on some leaf and faces to the upper, lower, left or right side. He can jump forward or to the left or right relative to his facing direction, but not backward or diagonally. For example, suppose he is facing to the left side, then he can jump to the left, upper and lower sides but not to the right side. In each jump, he will land on the nearest leaf on his jumping direction and face to that direction regardless of his previous state. The leaf he was on will vanish into the water after the jump. The goal of this puzzle is to jump from leaf to leaf until there is only one leaf remaining.
See the example shown in the figure below.
In this situation, he has three choices, namely, the leaves A, B and C. Note that he cannot jump to the leaf D since he cannot jump backward. Suppose that he choose the leaf B. After jumping there, the situation will change as shown in the following figure.
He can jump to either leaf E or F next.
After some struggles, he found this puzzle difficult, since there are a lot of leaves on the pond. Can you help him to find out a solution?
입력
H W
c1,1 ... c1,W
.
.
.
cH,1 ... cH,W
The first line of the input contains two positive integers H and W (1 ≤ H,W ≤ 10). The following H lines, which contain W characters each, describe the initial configuration of the leaves and the frog using following characters:
- '.’ : water
- ‘o’ : a leaf
- ‘U’ : a frog facing upward (i.e. to the upper side) on a leaf
- ‘D’ : a frog facing downward (i.e. to the lower side) on a leaf
- ‘L’ : a frog facing leftward (i.e. to the left side) on a leaf
- ‘R’ : a frog facing rightward (i.e. to the right side) on a leaf
You can assume that there is only one frog in each input. You can also assume that the total number of leaves (including the leaf the frog is initially on) is at most 30.
출력
Output a line consists of the characters ‘U’ (up), ‘D’ (down), ‘L’ (left) and ‘R’ (right) that describes a series of movements. The output should not contain any other characters, such as spaces. You can assume that there exists only one solution for each input.