최대한 빠르게

다오는 크기가 $H \times W$ 인 격자판 위에서 카트를 타며 이동하고 있다. 격자판의 몇몇 칸에는 박스 모양의 장애물이 있어서 카트가 들어가거나 지나갈 수 없으며, 다오는 매번 위, 아래, 왼쪽, 오른쪽 중 한 방향을 정해 일정 거리만큼 이동할 수 있다.

구체적으로, 처음에 다오는 원하는 방향으로 카트를 한 칸씩 움직일 수 있다. 격자판의 몇몇 칸에는 아이템이 놓여 있는데, 만약 다오의 카트가 정확히 아이템이 놓인 칸에서 멈추게 되면, 한 번에 이동할 수 있는 최대 거리가 영구적으로 $1$ 만큼 늘어나고 아이템은 격자판에서 사라진다. 즉, 지금까지 아이템을 $X$ 개 먹었다면, 매번 원하는 방향으로 최대 $X + 1$ 칸 움직일 수 있다. 단, 이동 중에 장애물이 있는 칸을 통과하거나 격자판 밖으로 나갈 수는 없다.

예를 들어, 아래 그림에서 다오가 지금까지 $1$ 개의 아이템을 먹었다고 하자. 아래와 오른쪽으로는 최대 $2$ 칸 이동할 수 있으며, 왼쪽으로는 장애물에 가로막혀 최대 $1$ 칸만 이동할 수 있다. 위로 $1$ 칸 이상 이동하면 격자판을 벗어나게 되므로 위로는 이동할 수 없다.

현재 다오의 위치, 격자판에 놓인 장애물과 아이템의 정보, 그리고 다오가 가고자 하는 목적지의 위치가 주어지면, 여러분은 이동 횟수를 최소화하면서 다오가 목적지까지 가는 경로를 구해야 한다.

입력 형식

첫 줄에 격자판의 크기를 나타내는 두 정수 $H$ 와 $W$ , 그리고 격자판에 놓인 아이템의 개수를 나타내는 정수 $K$ 가 공백으로 구분되어 주어진다. ( $13 \le H, W \le 49;$ $0 \le K \le 30$ )

이어지는 $H$ 개의 줄에는 격자판의 상태를 나타내는 길이 $W$ 의 문자열이 주어진다. 이 문자열은 문자 ., #, @, S, T로만 이루어져 있으며, 각각 빈 칸, 장애물이 놓인 칸, 아이템이 놓인 칸, 다오의 시작 위치, 다오의 목적지를 의미한다.

$H$ 개의 문자열 전체에서 문자 S와 T는 각각 정확히 $1$ 개 주어지며, 문자 @는 정확히 $K$ 개 주어진다.

출력 형식

첫 줄에 다오의 이동 횟수 $q$ 를 출력한다. $q \le 5\,000$ 를 만족해야 한다.

그다음 줄부터 총 $q$ 개의 줄에 걸쳐, 다오의 이동 방법을 나타내는 문자열을 출력한다. 이 문자열은 문자 $c$ 와 양의 정수 $d$ 로 이루어져 있어야 하며, 각각 이동 방향과 이동 거리를 의미한다. $c$ 는 문자 W, S, A, D 중 하나여야 하며, 각각 위, 아래, 왼쪽, 오른쪽 방향을 의미하고, $d$ 는 다오의 이동 거리를 의미한다.

예제

입력

5 5 4 @...@ .###. .#S#. .#@.@ T####

출력

5 S 1 D 2 W 3 A 4 S 4

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

미션 1 미션 2 미션 3 미션 4 미션 5 미션 6 미션 7 미션 8 미션 9 미션 10

이 문제의 총점은 모든 미션의 점수의 합으로 계산된다. 각 미션의 점수를 계산하는 방법은 다음과 같다.

$S$ : 미션에서 받을 수 있는 최대 점수
$P$ : 미션에 대한 참가자의 점수
$\alpha$ , $\beta$ : 미션마다 정해진 상수 (단, $\alpha>\beta$ )
$q$ : 참가자의 출력에서의 이동 횟수

P = \begin{cases}0 & q \ge \alpha \\ S \times \min\left(1, \dfrac{\alpha - q}{\alpha - \beta}\right) & q < \alpha \end{cases}

이때, 미션에 대한 참가자의 점수는 $P$ 를 $0.1$ 단위로 버림한 값이다. 즉, $\alpha$ 는 미션에서 $0$ 점을 받게 되는 이동 횟수의 하한, $\beta$ 는 미션에서 만점을 받기 위한 이동 횟수를 나타내는 상수이다.

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 제약 조건을 지키지 않는 등) $P = 0$ 이다.

각 미션의 정보는 다음과 같다.

#	$H$	$W$	$K$	$S$	$\alpha$	$\beta$
$1$	$13$	$17$	$2$	$5$	$300$	$32$
$2$	$17$	$17$	$15$	$6$	$18$	$17$
$3$	$30$	$30$	$0$	$7$	$60$	$47$
$4$	$28$	$28$	$0$	$8$	$120$	$102$
$5$	$30$	$15$	$1$	$9$	$78$	$73$
$6$	$30$	$30$	$1$	$10$	$190$	$185$
$7$	$29$	$29$	$15$	$12$	$70$	$55$
$8$	$30$	$30$	$30$	$13$	$75$	$74$
$9$	$49$	$49$	$30$	$14$	$90$	$85$
$10$	$49$	$49$	$30$	$16$	$80$	$73$

미션마다 만점을 받을 수 있는 출력이 존재함이 보장된다.

해설

아이템을 획득할 때마다 이동할 수 있는 최대 거리가 증가할 때, 시작점에서 도착점으로 가는 최단 거리를 찾는 문제입니다.

아이템이 없는 경우( $K = 0;$ 미션 3, 4)에는 그래프에서 최단 경로를 찾는 것과 똑같이 생각할 수 있고, 너비 우선 탐색(BFS)을 이용해 문제를 해결할 수 있습니다.

아이템이 존재하는 상황에서는 각 아이템을 최대 한 번만 획득할 수 있기 때문에, 아이템을 획득할 때마다 맵이 변하는 것을 반영해야 합니다. 예를 들어 아이템이 하나만 있는 경우( $K = 1;$ 미션 5, 6)에는 다음과 같이 거리 배열을 정의하여 너비 우선 탐색을 이용해 문제를 해결할 수 있습니다.

$D(i, j, 0)$ : 아이템을 획득하지 않고 $(i, j)$ 로 이동하기 위한 최단 거리
$D(i, j, 1)$ : 아이템을 획득하고 $(i, j)$ 로 이동하기 위한 최단 거리

아이템이 더 많이 존재할 때는 "지금까지 획득한 아이템의 집합"을 함께 관리해야 합니다. 즉, 아이템이 없을 때는 거리 배열에서 $NM$ 개, 아이템이 하나일 때는 $2 \times NM$ 개의 상태를 관리했다면, 아이템이 $K$ 개일 때는 $2^K \times NM$ 개의 상태를 관리해야 합니다. $K \le 15$ 정도로 아이템이 많지 않은 경우(미션 1, 2, 7)에는 $2^K \times NM$ 개의 상태를 모두 보는 것으로 $1$ 초 안에 답을 구할 수 있습니다.

$K > 15$ 로 아이템이 많은 경우(미션 8, 9, 10)에는 크기가 $2^K \times NM$ 인 배열을 선언하기 힘들기 때문에 다른 방법을 생각해야 합니다. 다양한 방법이 있지만, $10$ 초 안에 만점을 받을 수 있는 쉬운 방법 $2$ 개를 소개합니다. 두 방법 모두 일직선으로 연속한 길의 길이가 별로 길지 않음을 이용합니다.

무작위로 아이템 $10$ 개를 선택한 뒤 $K = 10$ 인 문제를 해결하는 것을 여러 번 반복
시작점과 멀리 있으면서 도착점과 가까운 아이템을 일부 삭제한 뒤 외판원 순회 문제(traveling salesman problem)처럼 $\mathcal{O}\left( 2^K \times K^2 \right)$ 시간에 해결