프로그램 명: coci_lunapark(special judge)
제한시간: 2 초

[문제 요약]행렬이 주어진다. 각 성분의 숫자는 즐거움의 정도를 나타낸다. 제일 위 왼쪽에서 제일 아래 오른쪽으로 가는 길을 출력하는게 문제. 두 번 가지 못하고 모든 길을 갈 필요는 없다.

최대 즐거움은 가는 길 상에 있는 숫자(즐거움)합이 최대인 길을 나타내고 , U(up), R(right), D(down), L(left) 로 방향을 나타낸다.

Mirko has grown tired of all the books, so he decided to go to the amusement park with his friends, despite not liking roller coasters. While his friends are having the time of their lives riding the coasters, Mirko is sitting on a bench, waiting and thinking about the possible paths of the coasters.

The amusement park’s area can be represented as a table of R rows by C columns. A roller coaster has to start from the upper left corner and end at the lower right corner of the table. Each cell can be visited at most once, but not all cells need to be visited. It can continue its path from the current cell to the adjacent one above, below, to the left, or to the right of it.

Each cell has a positive integer value associated with it, specifying how amusing that cell is to visitors. The total amusement value of the coaster is the sum of amusement values of all cells that the coaster visits. Help Mirko determine any one of the most amusing coasters (ones with the maximum sum).

입력

The first line of input contains two integers R and C (2 ≤ R, C ≤ 1000), the dimensions of the table.

Each of the next R lines contains C positive integers smaller than 1000, specifying the amusement values of the respective table cells.

출력

The first and only line of output must contain a sequence of letters with no blanks. The letters specify the sequence of directions that the coaster follows, starting from the upper left and ending at the lower right corner. The directions up, right, down, left are marked by letters ‘U’, ‘R’, ‘D’, ‘L’, respectively.

Note: The solution isn’t guaranteed to be unique.

입출력 예

입력

3 3
5 1 3
2 4 8
1 1 2

출력

RRDLLDRR

입력

2 2
2 1
3 4

출력

DR

출처:coci 2010
// special judge 가 아직...
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]