Informatica Online Judge

  미로찾기 (Large) [0190 / 00BE]

Time Limit(Test case) : 500(ms)
Number of users who solved : 229   Total Tried : 324


The Champion of this Problem (C++) : dsyun96 - 0ms / 1106byte
My Best Submission (C++) : N/A

[]

Background

크기가 H*W인 미로가 있다.

이 미로는 길과 벽으로 구성되어 있으며, 길은 ".", 벽은 "#"으로 구성되어 있다.

그리고 시작위치 "S"와 도착위치 "G"가 존재한다.

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

Input

첫 번째 줄에 H와 W가 공백으로 구분되어 입력된다. (단, H, W는 5이상 4000이하의 자연수이다.)
두 번째 줄부터 H줄에 걸쳐서 W개로 이루어진 문자열이 입력된다.

문자열은 길은 ".", 벽은 "#", 출발점은 "S", 도착점은 "G"로 표시된다. 그리고 S와 G의 위치는 서로 다르다.

Output

출발지로부터 도착지까지의 최단경로를 출력한다.

주어진 미로는 모두 답이 있다.

IO Example

입력
5 5
#S###
#...#
###.#
#....
###G#

출력
6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]