드리프트 주행

드리프트 주행 기술에 매력을 느낀 다오는 주행 중 드리프트 기술을 가능한 한 많이 적용하려고 한다. 왜냐하면, 방향을 자주 바꿀수록 자동차가 지나간 흔적, 즉 스키드 마크가 아름답게 형성된다고 생각하기 때문이다.

$H \times W$ 크기의 격자판의 맵이 있다. 다오는 이 맵에서 주행 연습을 하고 있다.

이 맵에서 위에서 $i$ 번째 줄, 왼쪽에서 $j$ 번째 칸에 있는 격자를 $(i, j)$라고 하자.

다오는 $(A, B)$에서 주행을 시작하고, $(C, D)$에서 주행을 마치고자 한다. 주행 시 매 순간 상하좌우로 인접한 격자 중 어느 곳으로 이동할지 결정해야 한다. 어떠한 결정을 해도 자동차 움직인 경로를 따라 스키드 마크가 남게 된다. 다오는 이를 통해 멋진 그림을 만들고자 한다.

다오가 주행 시 지켜야 할 규칙은 다음과 같다:

1. 자동차의 이동 경로를 나타내는 스키드 마크는 서로 겹치면 안 된다. 즉, 이전에 방문한 칸에 다시 방문할 수 없다.
2. 장애물이 있는 칸은 지나갈 수 없다.
3. 맵 밖으로 나갈 수 없다.

다오는 위의 주행 규칙을 따르면서 드리프트를 가능한 한 많이 하여 아름다운 그림을 만들려고 한다. 드리프트란, 좌우 $90$도로 방향 전환하는 것을 의미한다.

다오가 상하좌우로 인접한 격자로 이동하는 것을 각각 하나의 문자 W, S, A 혹은 D로 나타내자. 일반적인 쿼티 키보드에서 WASD의 배치를 생각하면 좋다. 주행 경로 문자열이란, 각 이동을 문자로 표현하여 순서대로 나열한 것이다.

아래 그림은 크기가 $3 \times 6$인 격자에서 다오가 $(3, 1)$에서 주행을 시작하여 $(3, 5)$에서 주행을 마칠 때, 다오가 이동한 경로를 예로 보여준다.

이때, 다오의 주행 경로 문자열은 DDWDWDDSSA이다. 이 경우, 다오는 총 $6$ 번의 드리프트를 했다.

맵에 대한 정보와 다오의 시작, 종료 위치가 주어질 때, 드리프트를 많이 하는 주행 경로 문자열을 출력하는 프로그램을 작성하시오.

입력 형식

첫 줄에 격자의 크기를 나타내는 두 정수 $H$와 $W$가 공백으로 구분되어 주어진다. ($3 \le H \le 35;$ $3 \le W \le 60$)

두 번째 줄에 다오의 시작 위치와 종료 위치를 나타내는 네 정수 $A$, $B$, $C$, $D$가 공백으로 구분되어 주어진다. ($1 \le A, C \le H;$ $1 \le B, D \le W;$ $(A, B) \ne (C, D)$)

이어지는 $H$ 개의 줄에 맵의 정보를 나타내는 $W$ 개의 문자가 주어진다. 주어지는 문자는 . 또는 #이며, 각각 차례대로 장애물이 없는 칸과 장애물이 있는 칸을 의미한다.

다오의 시작 위치와 종료 위치에 장애물이 있지 않으며, 시작 위치에서 종료 위치로 가는 주행 경로가 항상 존재하도록 입력이 주어진다.

출력 형식

첫 줄에 다오가 주행 중 드리프트한 횟수를 출력한다.

두 번째 줄에 다오의 주행 경로 문자열을 출력한다.

예제

3 6
3 1 3 5
......
##..#.
...#..

6
DDWDWDDSSA

채점 방식

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

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

• $S$ : 미션의 만점
• $P$ : 미션에 대한 참가자의 점수
• $\alpha$ : 각 미션에서 만점을 받을 수 있는 드리프트 횟수
• $L$ : 참가자의 출력에 따른 드리프트 횟수

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 주행 규칙을 모두 지키지 않는 등) $P = 0$이다.

편의상, $\Delta = \max\left\{ \left\lceil \frac{\alpha}{30} \right\rceil, 5 \right\}$ 라고 하자. 이때, $\lceil x \rceil$은 $x$ 이상의 가장 작은 정수를 의미한다. 모든 미션에서 $\Delta < \alpha$ 임에 유의하라.

1. $L \ge \alpha$ 인 경우: $P = S$
2. $\alpha - \Delta \le L < \alpha$ 인 경우: $\displaystyle P = \left( 0.5 + \frac{( L + \Delta - \alpha ) \times ( L + \Delta - \alpha )}{2 \times \Delta \times \Delta} \right) \times S$
3. $L < \alpha - \Delta$ 인 경우: $\displaystyle P = 0.5 \times \frac{L}{\alpha - \Delta} \times S$

이때, $P$는 최종적으로 $0.1$ 단위로 버림된다.

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

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

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

해설