문제1789--미로 찾기

1789: 미로 찾기

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MiB

문제 설명

크기가 h*w인 미로가 있다.


이 미로는 길과 벽으로 구성되어 있으며, 길은 ".", 벽은 "#"으로 구성되어 있으며, 시작위치 "S"와 도착위치 "G"가 존재한다.


위에서 제시한 각 정보가 주어질 때, S위치로부터 G위치까지의 최단 거리를 구하는 프로그램을 작성하시오

입력 설명

첫 번째 줄에 h와 w가 공백으로 구분되어 입력된다.
(단, h, w는 5 이상 100 이하의 자연수이다.)
두 번째 줄부터 h줄에 걸쳐서 w개로 이루어진 문자열이 입력된다.
문자열은 길은 ".", 벽은 "#", 출발점은 "S", 도착점은 "G"로 표시된다. 
그리고 S와 G의 위치는 서로 다르다

출력 설명

출발지로부터 도착지까지의 최단거리를 출력한다.
단, 도달할 수 없는 미로일 경우에는 -1을 출력한다.

입력 예시 Copy

5 5
#S###
#...#
#.#.#
#....
###G#

출력 예시 Copy

6