한꺼번에 길 찾기

$2$차원 평면상의 격자 모양 지도에서 주어진 물체가 목적지로 가는 최단 경로는 다익스트라 혹은 A* 알고리즘을 사용하여 계산할 수 있다. 그런데 실시간 전략 시뮬레이션 게임의 경우처럼, 여러 개의 유닛들이 동시에 움직이고 두 개 이상의 유닛이 동시에 한 칸에 함께 머무를 수 없다면 유닛들이 장애물의 역할을 하기 때문에 위의 알고리즘을 단순히 적용하여 계산하기는 어렵다.

아래와 같은 조건에서 모든 유닛을 해당 목적지까지 빠르게 이동하는 프로그램을 작성해 보자.

• 각 유닛에는 하나의 색이 배정되어 있다. 같은 색을 가진 여러 개의 유닛이 존재할 수 있고, 각 색마다 그 색을 가진 유닛 수만큼 목적지가 지정된다.
• 유닛에 배정되는 색의 가짓수는 최대 $2$개이다.
• 각 유닛은 시뮬레이션의 매 턴마다 상하좌우 중 하나의 방향으로 한 칸씩 한번만 이동하거나, 아니면 이동하지 않을 수 있다.
• 각 유닛은 턴의 시작 시점에 비어있는 칸으로만 이동할 수 있다. 따라서, 각 유닛은 옆 칸에 위치한 유닛이 다른 칸으로 이동하더라도 그 턴에서는 그 칸으로 이동할 수 없다.
• 매 턴마다 이동이 결정된 유닛들은 동시에 이동하고 해당 턴이 끝난다.
• 두 개 이상의 유닛이 동시에 한 칸에 머무를 수 없다. 따라서, 시뮬레이션의 시작 시점에 모든 유닛은 서로 다른 칸에 주어지며, 두개 이상의 유닛이 동시에 같은 칸으로 이동할 수 없다.
• 지도에서 장애물인 벽을 제외한 공간은 모두 서로 연결되어 있고, 유닛은 지도 밖으로 나갈 수 없다.
• 모든 턴을 마쳤을 때 유닛이 자신에게 배정된 색의 목적지들 가운데 하나에 위치할 경우에 그 유닛은 목적지에 도착한 것으로 정한다.

입력 형식

첫 줄에 지도의 세로 크기 $H$와 가로 크기 $W$가 주어진다. ($1 \le H \le 100$, $1 \le W \le 100$)

두번째 줄부터 $H$개의 줄에 걸쳐, 각 줄마다 $W$개의 글자로 구성된 지도가 입력된다. 지도에 있는 모든 글자는 #, ., A, B, a, b 중 하나이다. 지도를 읽는 규칙은 다음과 같다.

• # 은 장애물인 벽이다. 유닛은 벽으로 이동해 들어갈 수 없다.
• . 은 빈 공간이다. 유닛은 빈 공간으로 이동해 들어갈 수 있다.
• A 와 같이 알파벳 대문자는 그 대문자 색의 유닛 하나가 주어진 위치이다. 전체 유닛의 개수는 $100$이하이다.
• a 와 같이 알파벳 소문자는 그 알파벳의 대문자 색의 유닛 하나가 도착해야 할 목적지이다. 목적지는 유닛의 이동에 대하여는 빈 공간과 같이 이동해 들어가거나 나올 수 있다.

모든 테스트케이스에 대해, 입력 데이터가 어떤 식으로 구성되어 있는지 추상적으로 보여주는 그림 파일을 제공한다. 즉, 입력 데이터가 정확히 그림과 일치하지 않을 수 있다. 그림 파일은 다음과 같은 형식을 따른다.

• 유닛의 현재 위치는 안이 차있는 파란색/주황색 도형이다.
• 유닛의 도착지는 안이 비어있는 파란색/주황색 도형이다.
• 벽과 장애물은 검은색 부분이다.

그림 파일은 여기서 다운받을 수 있다. (링크)

출력 형식

• 첫 줄에 이동시키고자 하는 턴 수 $T$를 출력한다.
• 각 턴 마다 이동시키고자 하는 유닛의 개수 $N$을 출력한다.
• 다음 N줄에 걸쳐 <현재세로위치> <현재가로위치> <이동방향> 을 출력한다.
• <현재세로위치> 는 가장 위쪽이 $1$이며 가장 아래쪽이 $H$이다.
• <현재가로위치> 는 가장 왼쪽이 $1$이며 가장 오른쪽이 $W$이다.
• <이동방향>은 상=U, 하=D, 좌=L, 우=R이다.
• 유닛의 총 이동횟수는 $120\,000$번을 넘을 수 없다.

예제 1

2 5
bAB.a
#..##

4
1
1 3 D
2
1 2 R
2 3 L
2
1 3 R
2 2 U
2
1 4 R
1 2 L

예제 2

3 5
AB...
A###.
b..aa

6
1
2 1 D
2
1 1 D
3 1 R
3
1 2 L
2 1 D
3 2 R
3
1 1 D
3 1 R
3 3 R
3
2 1 D
3 2 R
3 4 R
1
3 3 R

채점 방식

각 테스트케이스의 점수는 아래와 같이 계산된다.

• 출력에 잘못된 내용이 있거나, 도착하지 못한 유닛이 전체 유닛의 절반을 넘는 경우 점수를 받지 못한다.
• 같은 입력으로 채점을 여러 번 수행하며, 여러 번의 채점에 대해 결과값이 달라지는 경우 점수를 받지 못한다.
• 위의 경우에 해당되지 않다면, 해당 테스트케이스의 패널티는 아래와 같이 계산된다. $$\textrm{\textbf{패널티}} = (\textrm{도착하지 못한 유닛 수}) \times 50 + (\textrm{턴 수})$$
• 여러분은 각 테스트케이스 마다 $(\textrm{해당 테스트케이스의 만점}) \times (B/T)$ 를 점수로 받는다.
• $T$ = 해당 테스트케이스에 대한 제출 답안 결과의 패널티
• $B$ = 해당 테스트케이스에 대해 모든 대회 참가자가 이 문제에 제출한 마지막 답안으로부터 나온 패널티 중 가장 작은 값

최종 점수는 모든 테스트케이스 점수의 합이다. 이와 같은 채점 방식 때문에 제출한 이후에 점수가 계속 변할 수 있다.

해설