시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB (추가 메모리 없음)124453948.148%

문제

국렬이는 연세대학교 신입생 프로그래밍 경진대회를 개최한 기념으로 공학관 근처 $N \times N$ 크기의 운동장에서 화석 발굴 이벤트를 진행하려고 했다. 그러나 공학관 내의 무수히 많은 실험으로 인해 운동장의 일부가 인체에 매우 위험한 물질로 오염되었기에 이 이벤트는 취소되었다. 다행히 우수한 연세대학교 신입생들의 도움을 받아서 오염되지 않은 흙을 공학관 근처 언덕으로 옮기는 작업을 마무리했다. 덕분에 국렬이는 드디어 화석 발굴 이벤트를 진행할 수 있게 되었다.

[그림] 화석의 사진

화석은 그림과 같이 정사각형 크기의 달팽이 형태로, 한 변의 길이는 무조건 $4k+1$ 꼴이다. 화석의 중심은 위에서 $2k+1$칸, 왼쪽에서 $2k+1$칸 떨어진 칸을 의미한다. ($k$는 양의 정수)

화석 발굴 이벤트는 공학관 근처 운동장에 묻힌 화석을 찾는 이벤트이다. 당신은 주어진 흙 속에서 화석들을 전부 찾아내야 한다.

입력

첫 번째 줄에 운동장의 한 변의 길이를 의미하는 양의 정수 $N$이 주어진다. ($5 \le N \le 1\,250$)

두 번째 줄부터 $N$개의 줄에 걸쳐서 운동장에 대한 정보가 주어진다. .은 흙만 있는 칸을 의미하고, #은 화석이 있는 칸을 의미한다. 입력으로 들어오는 화석의 형태는 언제나 달팽이 형태로만 나온다.

운동장에 최소 $1$개 이상의 화석이 묻혀있으며, 화석들은 붙어있거나 운동장 밖으로 빠져나온 경우는 주어지지 않는다.

출력

첫 번째 줄에 화석의 개수를 출력한다.

두 번째 줄부터 각 줄에 화석의 중심의 위치의 행 번호와 열 번호, 화석의 한 변의 길이, 그리고 화석의 방향을 출력한다. 화석의 정보는 화석의 중심 위치의 행 번호가 작은 것부터, 행 번호가 같은 경우 열 번호가 작은 것부터 출력한다.

예제 입력 1

11
#.###.###.#
#.#.#.#.#.#
#.#.#.#.#.#
#...#.#...#
#####.#####
...........
#####.#####
#...#.#...#
#.#.#.#.#.#
#.#.#.#.#.#
#.###.###.#

예제 출력 1

4
3 3 5 UL
3 9 5 UR
9 3 5 DL
9 9 5 DR

예제 입력 2

11
#####.#####
....#.#....
###.#.#.###
#...#.#...#
#####.#####
...........
#####.#####
#...#.#...#
###.#.#.###
....#.#....
#####.#####

예제 출력 2

4
3 3 5 LU
3 9 5 RU
9 3 5 LD
9 9 5 RD

노트

달팽이들의 방향은 다음과 같이 표기한다.

UL UR
LU RU
LD RD
DL DR

출처

University > 연세대학교 > 2021 연세대학교 프로그래밍 경진대회 E번