32636번 - 근수의 미로게임

문제

근수와 승형이는 근수의 미로게임을 즐기려고 한다. 미로는 $N \times M$ 크기의 격자판으로 이루어져 있으며, 빈 칸, 장애물, 시작점, 도착점으로 이루어져 있다. 미로에 시작점은 단 한 개 존재하며 도착점은 한 개 이상 존재할 수도, 존재하지 않을 수도 있다.

현재 근수는 시작점에 있다. 모든 도착점에는 근수가 좋아하는 도마 우마루 인형이 있어서 근수는 도착점 중 한 곳으로 이동하고 싶어 한다. 승형이는 이러한 근수가 못마땅한지 근수를 최대한 방해하려고 한다. 근수와 승형이는 한 턴마다 다음과 같은 행동을 게임이 끝나기 전까지 반복한다.

1. 현재 있는 위치가 도착점이라면 근수가 게임에서 승리한다.
2. 현재 있는 위치가 도착점이 아니라면, 승형이는 네 방향(위, 아래, 왼쪽, 오른쪽) 중 하나를 선택한다.
3. 근수는 승형이가 선택한 방향을 제외한 세 방향 중 한 방향을 선택해서 그 방향으로 한 칸 움직인다. 움직이려고 하는 위치에 장애물이 있으면 그 즉시 승형이가 게임에서 승리하며, 움직인 곳이 이미 방문했던 장소거나 격자판 밖이라면 그 즉시 승형이가 게임에서 승리한다.

근수는 게임을 이기고 싶어하고, 이긴다면 근수가 도착점에 도달하는 턴 수를 최대한 줄이고 싶어한다. 승형이는 게임을 이기고 싶어하고, 이기지 못한다면 근수가 도착점에 도달하는 턴 수를 최대한 늘리고 싶어한다. 근수와 승형이가 항상 최선의 전략으로 게임을 한다고 가정할 때 근수가 게임에서 이길 수 있는지, 이긴다면 도착점에 도달할 때까지 얼마나 걸리는지 구해보자.

입력

첫 번째 줄에 미로의 크기인 $N,ドル $M$이 주어진다 $(1 \leq N, M \leq 500)$

두 번째 줄부터 $N+1$번째 줄까지 미로에 대한 정보가 주어진다. .은 빈 칸, #은 장애물, S는 시작점, G는 도착점을 의미한다. 미로에 시작점은 단 한 개 존재하며 도착점은 한 개 이상 존재할 수도, 존재하지 않을 수도 있다.

출력

근수와 승형이가 항상 최선의 전략으로 게임을 한다고 가정할 때 근수가 도착점에 도달하는 턴 수를 출력한다. 만약 근수가 게임에서 이길 수 없다면 -1을 출력한다.

제한

힌트