미니 골프

당신은 $R \times C$ 격자에서 미니 골프를 하고 있다. 한 번 칠 때마다 골프공을 위, 아래, 오른쪽, 왼쪽의 네 방향 중 하나로 직선으로 최대 $K$칸까지 임의의 칸 수만큼 퍼팅할 수 있다. 물론 공을 벽 너머로 또는 코스 밖으로 퍼팅할 수는 없다.

당신의 과제는 공을 홀에 넣는 데 필요한 최소 퍼팅 횟수를 계산하는 것이다.

배점

당신의 풀이는 여러 테스트 케이스 그룹으로 나누어 채점된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제약 조건

$1$ |$8$| 입력에 벽(”#”)이 없다.

$2$ |$18$| $R = 2$

$3$ |$22$| $1\le R,C,K\le 100$

$4$ |$25$| $K \ge \text{max}(R,C)$, 다시 말해 퍼팅할 수 있는 거리에 제한이 없다.

$5$ |$27$| 추가 제약 조건이 없다.

첫째 줄에 세 정수 $R$, $C$, $K$ ($1 \leq R \times C \leq 10^6$, $1 \leq K \leq 10^6$)가 주어진다. 이들은 각각 행의 수, 열의 수, 한 번에 퍼팅할 수 있는 최대 거리이다.

다음 $R$개의 줄에는 각각 미니 골프 코스를 나타내는 $C$자 문자열이 주어진다.

• ”.”는 칸이 비어 있음을 의미한다.

• ”#”는 칸에 벽이 있음을 의미한다.

• ”S”는 이 칸이 시작점임을 의미한다. 입력에는 ”S”가 정확히 하나 있다.

• ”G”는 이 칸에 홀이 있음을 의미한다. 입력에는 ”G”가 정확히 하나 있다.

시작 칸에서 홀에 도달할 수 있음이 보장된다.

공을 홀에 넣는 데 필요한 최소 퍼팅 횟수를 정수로 출력한다.