33280번 - 배틀쉽 스페셜 저지

문제

보드게임 배틀쉽은 $N\times M$ 격자판 위에서 진행된다. $NM$개의 칸 중 $K$개의 칸은 벽이다. 벽이 아닌 모든 칸들은 상하좌우로 서로 연결되어 있다. $(0\le K<NM)$

벽이 아닌 어떤 칸에 말이 $NM-K$개 올려져 있을 때, 하늘이는 다음 행위를 반복하여 벽이 아닌 모든 칸에 말을 정확히 한 개씩 배치하려고 한다.

1. 말이 2ドル$개 이상 놓여져 있는 칸을 선택해 말을 1ドル$개 이상 가져간다. 단, 말을 적어도 하나 남겨두어야 한다.
2. 왼쪽, 오른쪽, 위쪽, 아래쪽 중 한 방향을 선택한 뒤 벽이 등장하거나, 말이 놓여있거나, 격자판을 벗어나기 직전까지 이동한다. 이 때 최소 한 칸 이동하여야 한다.
3. 도착한 칸에 가져갔던 말을 전부 놓는다.

하늘이가 목표를 달성할 수 있는지 판별하고 가능하다면 방법을 하나 출력해보자. 만약 방법이 여러 가지라면 아무거나 출력해도 된다.

입력

첫째 줄에 $N,ドル $M$이 공백을 사이에 두고 주어진다. $(1 \leq N,M \leq 500)$

둘째 줄부터 $N$개의 줄에 걸쳐 격자판을 나타내는 길이 $M$의 문자열이 주어진다. 문자열은 #과 .로만 이루어져 있으며 #은 벽을, .은 벽이 아닌 칸을 의미한다. 모든 .은 상하좌우로 서로 연결되어 있다.

$N+2$번째 줄에 말이 놓여있는 칸을 나타내는 정수 $R,ドル $C$가 공백을 사이에 두고 주어진다. 이는 위에서 $R$번째 행, 왼쪽에서 $C$번째 열임을 의미한다. 해당 칸은 벽이 아니다. $(1 \leq R \leq N;$ 1ドル \leq C \leq M)$

출력

첫째 줄에 하늘이가 목표를 달성할 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

달성할 수 있다면 가능하다면 둘째 줄에 행위를 반복하는 횟수 $V$를 출력하고, 셋째 줄 부터 $V$개의 줄에 걸쳐 다음과 같은 형식으로 방법을 출력한다.

• $r,円 c,円 n,円 d$: $(r,c)$ 칸에서 $n$개의 말을 가져가 $d$ 방향으로 최대한 이동한 후 말을 놓는다.

$(r,c)$ 칸은 위에서 $r$번째 행, 왼쪽에서 $c$번째 열에 해당하는 칸으로, 말이 $n$개보다 많이 놓여있고 벽이 아니어야 한다. $d$는 왼쪽, 오른쪽, 위쪽, 아래쪽 각각 L, R, U, D의 값을 가지며, 한 칸 이상 이동이 가능한 방향이어야 한다.

위의 조건을 지키지 않으면 틀렸습니다를 받음에 유의하시오.

제한

힌트