세탁소의 송풍 신호

문제

한 세탁소는 건조실 바닥을 R행 C열의 같은 크기 칸으로 나누어 관리한다. 각 칸은 옷걸이가 놓인 칸, 송풍 장치가 놓인 칸, 또는 막힌 칸 중 하나다. 건조실의 상태를 나타내는 지도에서 옷걸이 칸은 마침표 `.`, 송풍 장치 칸은 대문자 `F`, 막힌 칸은 `#`으로 표시한다. 하나의 칸에 두 종류의 시설이 함께 놓이는 경우는 없다. 직원은 모든 옷걸이에 송풍 시작 신호가 전달되는 시간을 확인하려고 한다. 시각 0에 모든 송풍 장치 칸이 동시에 신호를 받은 상태가 된다. 이후 신호를 받은 칸은 정확히 1분 뒤에 자신의 상하좌우로 인접한 칸 중 막히지 않은 칸에 신호를 전달한다. 대각선 방향으로는 전달하지 않으며, 건조실 지도 밖으로도 전달하지 않는다. 막힌 칸은 신호를 받거나 전달할 수 없다. 옷걸이 칸과 송풍 장치 칸은 모두 신호를 전달할 수 있다. 어떤 칸이 여러 방향에서 신호를 받는다면 가장 먼저 도착한 시각을 그 칸의 수신 시각으로 정한다. 이미 신호를 받은 칸이 나중에 다시 신호를 받더라도 수신 시각은 바뀌지 않는다. 한 칸은 인접한 여러 칸에 동시에 신호를 전달할 수 있으므로, 신호가 갈라져 퍼지는 데 추가 시간은 들지 않는다. 지도에는 송풍 장치가 여러 개 있을 수도 있고 하나도 없을 수도 있다. 모든 송풍 장치는 같은 시각에 작동하며 어느 장치에서 출발한 신호인지는 구분하지 않는다. 신호가 도달하지 못하는 옷걸이 칸이 하나라도 있으면 전체 옷걸이의 수신을 완료할 수 없다. 막힌 칸 자체에는 신호를 전달할 필요가 없다. 모든 옷걸이 칸이 신호를 받은 상태가 되는 가장 이른 시각을 분 단위 정수로 구해야 한다. 끝내 신호를 받지 못하는 옷걸이 칸이 있다면 -1을 출력한다. 옷걸이 칸이 처음부터 하나도 없다면 송풍 장치의 존재 여부와 관계없이 시각 0에 조건을 만족한 것으로 본다.

입력

첫째 줄에 행 수 R과 열 수 C가 공백으로 구분되어 주어진다. R과 C는 각각 1 이상 300 이하의 정수다.
다음 R개 줄에 건조실 지도가 주어진다. 각 줄은 길이가 C인 문자열이며 `.`, `F`, `#`으로만 이루어진다.

출력

모든 옷걸이 칸에 신호가 도달하는 가장 이른 시각을 정수 하나로 출력한다. 도달할 수 없는 옷걸이 칸이 있으면 -1을 출력한다. 옷걸이 칸이 없으면 0을 출력한다.

3 5
F..#.
.#...
...#F

4

2 3
F#.
.#.

-1

1 3
###

0

출처: Devin.KR 자체 제작