문제 설명
세종이는 프로그래밍 경진대회 이벤트로 보물 찾기를 준비하였다. 보물찾기는 n * n으로 이루어진 지도에서 보물을 찾아 출구로 나오는 식으로 진행된다.
예를 들어 보물 지도가 아래와 같이 주어질 때, 세종이는 입구 S에서 T까지 최소 6번을 이동하여 보물을 획득하고 보물 획득 후 최소 5번 이동하여 출구 G에 도착할 수 있다. 이렇게 최소 11번의 이동으로 S에서 시작하여 T를 획득하고 G에 도착할 수 있다.
(#: 벽, S: 입구, T: 보물, G: 출구, .: 이동 가능)
보물 지도가 주어질 때, 입구에서부터 보물을 찾아 출구로 빠져나오는 최소 횟수를 구하는 프로그램을 작성하시오.
예를 들어 보물 지도가 아래와 같이 주어질 때, 세종이는 입구 S에서 T까지 최소 6번을 이동하여 보물을 획득하고 보물 획득 후 최소 5번 이동하여 출구 G에 도착할 수 있다. 이렇게 최소 11번의 이동으로 S에서 시작하여 T를 획득하고 G에 도착할 수 있다.
| # | # | # | # | # | # |
| # | S | # | # | G | # |
| # | . | # | . | . | # |
| # | . | . | . | # | # |
| # | . | # | . | T | # |
| # | # | # | # | # | # |
(#: 벽, S: 입구, T: 보물, G: 출구, .: 이동 가능)
보물 지도가 주어질 때, 입구에서부터 보물을 찾아 출구로 빠져나오는 최소 횟수를 구하는 프로그램을 작성하시오.
입력 설명
첫 번째 줄에 지도의 크기 n이 입력된다.
두 번째 줄부터 지도가 입력된다. 단, 보물 지도의 바깥쪽은 모두 벽으로 둘러쌓여있다.
\(2 \le n \le 1,000\)
두 번째 줄부터 지도가 입력된다. 단, 보물 지도의 바깥쪽은 모두 벽으로 둘러쌓여있다.
\(2 \le n \le 1,000\)
출력 설명
최소 이동 횟수를 출력한다.
입력 예시 Copy
6
######
#S##G#
#.#..#
#...##
#.#.T#
######
출력 예시 Copy
11