십자말풀이

소 베시는 십자말풀이를 즐겨 푼다. 안타깝게도 여동생 엘시가 베시의 책에 우유를 온통 쏟는 바람에, 각 힌트가 어디서 시작하는지 알아보기 어려워졌다. 베시가 힌트 번호를 복원하도록 돕는 것이 여러분의 일이다!

번호가 없는 십자말풀이가 N x M 격자(3 <= N <= 50, 3 <= M <= 50)로 주어진다. 어떤 칸은 비어 있고 어떤 칸은 막혀 있다. 힌트 번호 매기기는 두 단계로 이루어진다.

1단계: 어떤 칸이 비어 있고, 왼쪽 이웃 칸이 막혀 있거나 격자 밖이며, 오른쪽 두 칸이 비어 있으면 그 칸은 가로 힌트를 시작한다(즉 가로 힌트는 3글자 이상의 단어를 나타낸다). 세로 힌트의 규칙도 마찬가지다(위 칸이 막혀 있거나 격자 밖이어야 하고, 아래 두 칸이 비어 있어야 한다).

2단계: 힌트를 시작하는 각 칸에 읽기 순서(맨 윗 행을 왼쪽에서 오른쪽으로, 그다음 행, 이런 식)로 1부터 차례대로 번호를 매긴다. 힌트를 시작하는 칸에만 번호가 매겨진다.

입력으로 주어지는 십자말풀이는 출판되는 십자말풀이에서 흔히 요구되는 조건들을 만족하지 않을 수 있다는 점에 유의하라. 어떤 빈 칸은 어느 힌트에도 속하지 않을 수 있다.

첫째 줄: 공백으로 구분된 N과 M이 주어진다.

둘째 줄부터 1+N째 줄까지: 각 줄은 격자의 한 행을 M개의 문자로 나타내며, 각 문자는 '.'(빈 칸) 또는 '#'(막힌 칸)이다.

첫째 줄에 힌트의 개수를 출력한다. 나머지 각 줄에는 힌트 하나의 행과 열을 (위에서 설명한 순서대로) 출력한다. 왼쪽 위 칸의 위치는 (1, 1)이다.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Bronze