배찌와 다오의 대청소 (스텝 업)

배찌는 봄을 맞아 대청소를 하려고 합니다.

배찌의 집은 세로 $N$ 칸, 가로 $M$ 칸으로 이루어진 격자로 나타낼 수 있습니다. 각 칸은 빈 칸, 장애물, 블럭 중 하나입니다. 배찌는 혼자서, 또는 친구 다오와 함께 물풍선으로 집에 있는 모든 블럭을 없애려고 합니다.

처음에 배찌와 다오는 각자 서로 다른 빈칸 중 하나에 서 있습니다. 배찌와 다오는 이동과 물폭탄 터트리기 중 하나를 골라 행동하는 것을 반복합니다. 만약 배찌와 다오가 같이 청소를 하고 있다면, 배찌부터 시작해서 번갈아가면서 행동합니다.

이동을 선택했다면, 배찌 또는 다오는 상하좌우 중 인접한 칸 하나를 골라 그 칸으로 움직일 수 있습니다.

장애물 또는 블럭이 있는 칸으로 이동하거나 집 밖으로 이동하는 것은 불가능합니다.
배찌 또는 다오가 서 있는 칸으로는 서로 이동할 수 있습니다.

물폭탄 터트리기를 선택했다면, 즉시 4개의 물줄기가 상하좌우 각 방향으로 나아갑니다.

물줄기가 블럭에 부딫힌다면 물줄기는 블럭과 같이 사라지고, 블럭은 빈 칸이 됩니다.
물줄기는 최대 $K$ 칸 나아간 뒤 사라집니다. 즉, 물폭탄을 터트린 캐릭터와 파괴된 블럭의 거리는 $K$ 이하입니다.
물줄기가 나아가는 도중 장애물이나 집 끝에 도달하면 물줄기는 멈춥니다.
배찌와 다오의 물줄기의 세기 $K$ 는 다를 수 있습니다.

배찌와 다오는 최소한의 움직임으로 모든 블럭을 터트리려고 합니다. 배찌와 다오의 청소를 도와줍시다!

입력 형식

첫째 줄에 정수 $N, M, C$ 가 공백으로 구분되어 주어집니다. $C = 1$ 이라면 배찌만, $C = 2$ 인 경우 배찌와 다오가 같이 움직입니다.

둘째 줄에 $C = 1$ 이라면 $K_1$ 이, $C = 2$ 라면 $K_1, K_2$ 가 공백으로 구분되어 주어집니다. $K_1$ 은 배찌의 물줄기 세기, $K_2$ 는 다오의 물줄기 세기입니다.

다음 $N$ 개의 줄에 걸쳐 집의 상태를 나타내는 길이 $M$ 의 문자열이 주어집니다. $i$ 번째 문자열의 $j$ 번째 문자는, 위에서 부터 $i$ 번째 행, 왼쪽에서부터 $j$ 번째 열에 해당하는 칸의 상태를 나타냅니다. 각 문자의 의미는 다음과 같습니다.

.: 빈 칸
#: 장애물
@: 블럭
B: 초기에 배찌가 있는 빈 칸
D: 초기에 다오가 있는 빈 칸

단, 입력에 B는 정확히 한 개, D는 $C=2$ 인 경우에만 정확히 한 개 주어지며, 모든 블럭을 파괴할 수 있는 입력만 주어집니다.

출력 형식

배찌의 행동을 나타내는 U, D, L, R, B로 이루어진 길이 $1$ 이상 $100\,000$ 이하의 문자열을 출력합니다.

각 문자의 의미는 다음과 같습니다.

U: 위로 이동
D: 아래로 이동
L: 왼쪽으로 이동
R: 오른쪽으로 이동
B: 물폭탄을 터트림

$C = 1$ 인 경우 배찌의 행동을 차례대로, $C = 2$ 인 경우, 배찌와 다오의 행동을 번갈아가며 출력합니다.

제한

$1 \le N \le 50$
$1 \le M \le 50$
$C$ 는 $1$ 또는 $2$
$1 \le K_1, K_2 \le 5$

채점

스텝 업 문제는 전체 문제의 점수의 20% 비중을 차지합니다.

올바르지 않은 출력을 한 경우 오답이 되며 점수는 $0$ 점입니다. 올바르지 않은 출력의 예시는 다음과 같습니다.

출력 형식을 맞추지 않은 경우
장애물이나 블럭이 있는 칸으로 이동한 경우
집 밖으로 이동한 경우

각 테스트케이스에 대한 비용 $\textrm{Cost}$ 는 다음과 같이 정해집니다.

모든 행동이 끝나고 파괴되지 않은 블럭의 수를 $X$ $X$ , 출력한 문자열의 길이를 $T$ $T$ 라고 합시다.
- $X = 0$ 인 경우 $\textrm{Cost} = T$
- $X \ne 0$ 인 경우 $\textrm{Cost} = 100\,000 + X$
비용이 낮을수록 더 좋은 결과입니다.

각 테스트케이스당 실제 점수는 배점 $S$ 와 기준 점수 $\textrm{Cost}'$ 에 대해 $\left\lfloor S \times \min\left(\frac{\textrm{Cost}'}{\textrm{Cost}}, 1\right) \right\rfloor$ 로 정해집니다. 각 테스트케이스의 배점과 기준 점수는 다음과 같습니다:

번호	$N$	$M$	$C$	$\textrm{Cost}'$	$S$
01	$3$	$3$	$1$	$1$	$50\,000$
02	$1$	$5$	$1$	$4$	$50\,000$
03	$5$	$5$	$2$	$3$	$50\,000$
04	$5$	$7$	$1$	$9$	$50\,000$
05	$6$	$7$	$1$	$18$	$50\,000$
06	$4$	$5$	$1$	$12$	$50\,000$
07	$13$	$13$	$1$	$37$	$50\,000$
08	$20$	$20$	$2$	$129$	$50\,000$
09	$20$	$20$	$2$	$151$	$50\,000$
10	$16$	$16$	$1$	$127$	$50\,000$
11	$17$	$18$	$2$	$80$	$100\,000$
12	$13$	$13$	$2$	$37$	$100\,000$
13	$15$	$15$	$2$	$35$	$100\,000$
14	$20$	$20$	$2$	$238$	$100\,000$
15	$20$	$20$	$2$	$72$	$100\,000$

스텝 업 문제에서의 최종 점수는 모든 테스트케이스의 점수의 합입니다.

시뮬레이터

문제 풀이를 돕기 위해, 시뮬레이터가 제공됩니다. 바로가기

우하단에서 미션을 선택하면 자동으로 시뮬레이터가 미션에 해당하는 입력을 보여줍니다.

시뮬레이터에서 문제를 해결했다면, "출력" 탭에서 본인의 답안을 텍스트 형태로 확인할 수 있습니다.

원한다면 출력된 본인의 답안을 그대로 제출할 수 있습니다. 문제를 푸는 데 시뮬레이터를 필수적으로 사용해야 하는 것은 아닙니다.

아래 버튼을 누르면 각 번호에 해당하는 입력이 열립니다.

미션 1 미션 2 미션 3 미션 4 미션 5 미션 6 미션 7 미션 8 미션 9 미션 10 미션 11 미션 12 미션 13 미션 14 미션 15