롤러코스터

시간 제한1초메모리 제한256 MB

요약

최대 1000x1000 격자에서 좌상단부터 우하단까지 셀을 중복 방문하지 않고 이동하며 방문한 칸의 값 합이 최대가 되는 경로를 찾는 문제입니다.

문제

한 놀이공원 운영자는 새 롤러코스터를 만들 직사각형 부지를 얻었다. 이 부지는 R행 C열의 격자로 나뉘어 있다.

롤러코스터는 왼쪽 위 칸에서 출발해 오른쪽 아래 칸에 도착해야 한다. 한 번 움직일 때마다 현재 칸과 상하좌우로 인접한 칸으로 이동할 수 있다. 같은 칸은 두 번 이상 방문할 수 없으며, 모든 칸을 반드시 방문할 필요는 없다.

각 칸에는 그 칸을 지날 때 탑승자가 얻는 기쁨의 값이 적혀 있다. 롤러코스터를 탄 사람이 얻는 전체 기쁨은 방문한 칸들의 기쁨의 합이다.

전체 기쁨이 최대가 되도록 롤러코스터가 이동하는 방법을 구하시오.

첫째 줄에 행의 수 R과 열의 수 C가 주어진다. (2 <= R, C <= 1000)

다음 R개 줄에는 각 칸을 지날 때 얻는 기쁨이 주어진다. 각 값은 1000보다 작은 양의 정수이다.

첫째 줄에 왼쪽 위 칸에서 오른쪽 아래 칸까지 이동하는 경로를 출력한다.

위쪽으로 이동하면 U, 오른쪽으로 이동하면 R, 왼쪽으로 이동하면 L, 아래쪽으로 이동하면 D를 출력한다.

최대 기쁨을 주는 경로가 여러 개라면 그중 아무거나 출력해도 된다.