신호가 모두 도착하는 시간

격자에서 모든 시작 칸이 동시에 신호를 보내요. S는 시작 칸, T는 신호를 받아야 하는 칸, .은 통과할 수 있는 칸, #는 벽이에요.

시간 0에 모든 S가 신호를 갖고, 매 시간마다 신호가 있는 칸에서 상하좌우의 벽이 아닌 이웃 칸으로 신호가 전해져요. 도착한 신호는 다음 시간에도 남아 있어요. T와 S도 신호가 통과할 수 있어요.

int solution(vector<string> board)를 작성해 모든 T가 신호를 받은 최초 시간을 반환해 주세요. T가 하나라도 도달 불가능하면 -1을 반환해요. T가 없으면 S의 유무와 관계없이 0이에요. T가 아닌 칸 전체에 신호를 보내야 하는 것은 아니에요.

매개변수와 반환값

행 수와 열 수는 각각 110, 모든 행의 길이는 같아요. 문자는 S, T, ., # 중 하나예요. S와 T의 개수는 각각 0100이에요. 격자는 비어 있지 않아요. 반환형은 int예요. 도달 가능하면 답은 0~99예요.

예시

1. ["S.T",".#.","T.S"] → 2: 위쪽 T는 왼쪽 위 S에서 두 칸, 아래쪽 T는 오른쪽 아래 S에서 두 칸 떨어져 있어요. 두 신호가 동시에 움직이므로 모두 2에 도착해요.
2. ["S#T","..."] → 4: 벽을 돌아 아래·오른쪽·오른쪽·위로 네 번 이동해야 해요.

자동 채점 입력·출력

첫 줄은 행 수 R과 열 수 C, 다음 R줄은 격자 문자열이에요. 최초 시간 또는 -1을 한 줄에 출력해요. 아래 하네스가 입력을 매개변수로 바꾸므로 solution만 작성해요.

3 3
S.T
.#.
T.S

2

2 3
S#T
...

4