농장의 급수 신호

문제

한 농장은 여러 구역의 급수 장치를 한꺼번에 작동시키기 위해 이웃한 장치끼리 신호를 전달하는 방식을 사용한다. 농장의 지도는 R행 C열의 직사각형 격자이다. 각 칸은 작물을 기르는 재배 칸, 신호를 처음 보내는 송신기 칸, 또는 장치가 설치되지 않은 막힌 칸 중 하나이다. 지도에서는 이들을 각각 문자 '.', 'S', '#'으로 나타낸다. 송신기는 하나 이상 설치되어 있다. 시각 0에 모든 송신기가 동시에 신호를 받는다. 신호를 받은 재배 칸이나 송신기 칸은 정확히 1분 뒤에 자신의 상하좌우로 인접한 칸에 신호를 전달한다. 이때 지도 밖이나 막힌 칸에는 신호를 전달할 수 없다. 대각선으로 맞닿은 칸 사이에도 직접 전달할 수 없다. 각 칸은 처음 신호를 받은 시각만 기록하며, 나중에 같은 신호가 다시 도착해도 기록을 바꾸지 않는다. 신호 전달은 모든 위치에서 동시에 이루어진다. 예를 들어 서로 다른 두 송신기에서 출발한 신호가 같은 재배 칸을 향해 이동한다면, 그 칸은 더 먼저 도착한 신호를 받는다. 어느 송신기에서도 도달할 수 없는 재배 칸은 시간이 아무리 지나도 신호를 받지 못한다. 송신기 칸은 신호가 이동하는 통로가 될 수 있지만, 급수 완료 여부를 조사하는 재배 칸의 개수에는 포함하지 않는다. 농장 관리자는 모든 재배 칸이 신호를 받는지 확인하려 한다. 모든 재배 칸이 신호를 받는다면, 마지막 재배 칸에 신호가 도착하는 시각과 바로 그 시각에 처음 신호를 받는 재배 칸의 수를 구한다. 재배 칸이 하나도 없는 지도도 주어질 수 있으며, 이 경우에는 완료 시각과 해당 칸의 수를 모두 0으로 정한다.

입력

첫째 줄에 정수 R과 C가 공백으로 주어진다. 1 ≤ R, C ≤ 300이다.
다음 R개 줄에 각각 길이가 C인 문자열이 주어진다. 각 문자는 '.', 'S', '#' 중 하나이다. 지도에는 'S'가 적어도 하나 있다.

출력

신호를 받지 못하는 재배 칸이 하나라도 있으면 -1만 출력한다. 그렇지 않으면 마지막 도착 시각과 그 시각에 처음 신호를 받는 재배 칸의 수를 한 줄에 공백으로 구분하여 출력한다. 재배 칸이 없으면 0 0을 출력한다.

3 5
S...S
.###.
.....

4 1

2 4
S#..
##.#

-1

1 3
S#S

0 0

출처: Devin.KR 자체 제작