1524: [2021 세종 정올 예선 N] 세종이의 보물찾기 1

세종이는 프로그래밍 경진대회 이벤트로 보물 찾기를 준비하였다. 
보물찾기는 n * n으로 이루어진 지 도에서 보물을 찾아 출구로 나오는 식으로 진행된다.
예를 들어 보물 지도가 아래와 같이 주어질 때, 세종이는 입구 S에서 T까지 최소 6번을 이동하여 보물을 획득하고 보물 획득 후 최소 5번 이동하여 출구 G에 도착할 수 있다. 
이렇게 최소 11번의 이동으로 S에서 시작하여 T를 획득하고 G에 도착할 수 있다.

#	#	#	#	#	#
#	S	#	#	G	#
#	.	#	.	.	#
#	.	.	.	#	#
#	.	#	.	T	#
#	#	#	#	#	#

 (# : 벽, S: 입구, T: 보물,  G: 출구,  . : 이동 가능)

첫 번째 줄에 지도의 크기 n이 입력된다.
두 번째 줄부터 지도가 입력된다. 단, 보물 지도의 바깥쪽은 모두 벽으로 둘러쌓여있다.
(2 <= n <= 1,000)

최소 이동 횟수를 출력한다.

6
######
#S##G#
#.#..#
#...##
#.#.T#
######

11