재난 대응 센터는 \(R \times C\) 크기의 도시 지도에 \(K\)개의 대피소를 설치했다. 지도의 각 칸은 이동 가능한 도로(\(.\))이거나 통과 불가능한 건물(\(\#\))이다. 대피소는 도로 위에 설치되며, 대피소 칸은 \(S\)로 표시된다.

시민들은 상하좌우로 인접한 칸으로 한 번씩 이동할 수 있고, 건물로는 이동할 수 없다. 각 도로 칸에서 가장 가까운 대피소까지의 최단 거리를 그 칸의 대피 거리라 한다.

도달 가능한 모든 도로 칸의 대피 거리 중 최댓값을 구하여라. 대피소에서 도달 가능한 도로 칸이 대피소 자신뿐이면 \(0\)을 출력한다.

• \(1 \le R, C \le 1\,000\)
• \(1 \le K \le R \times C\)
• 대피소는 반드시 도로 칸 위에 설치된다.
• 대피소가 아닌 도달 가능한 칸이 없을 수 있다.

첫째 줄에 행의 수 \(R\), 열의 수 \(C\), 대피소의 수 \(K\)가 공백으로 구분되어 주어진다.

다음 \(R\)개의 줄에 지도의 각 행이 주어진다. 각 행은 \(C\)개의 문자로 이루어지며 \(.\), \(\#\), \(S\) 중 하나이다.

도달 가능한 모든 도로 칸의 대피 거리 중 최댓값을 출력한다. 대피소 이외의 도달 가능한 칸이 없으면 \(0\)을 출력한다.

riseoj 작성

출처 Original