#2158 추노

1 s   128 MB  

Description

마라톤 선수 신승규는 '문도'라는 노예를 부리며 살아가고 있다.
 
'문도'는 평소에도 주인에게 자주 대들지만 승규는 별일이 없는 이상 내버려두었었다. 그러자 '문도'는 결국 주인이 가장 아끼는 물건을 훔쳐 달아나기로 하고 이날 밤 물건을 몰래 훔쳐 달아났다. 승규는 매우 돈이 많았기 때문에 경비업체를 고용했었었고, 경비업체가 그 광경을 목격하여 승규에게 알렸다.
 
승규는 평소에 '문도'로 인해 쌓여있던 분노를 표출하며 '문도'를 잡으러 직접 쫓아 갔다. 이 사실을 안 '문도'는 승규로부터 열심히 도망치며 길을 헤매다가 미로에 들어가게 되었다! 집 밖으로 나온 적이 없던 '문도'는 당연히 미로에 대한 길을 알 수 없었다. 그리고 촉박하게 도망가야 했던 것이 승규가 계속 쫓아오기 때문에 빠르게 길을 찾아야 했다.  
 
이때 '문도'는 운이 좋게도 처음 출발 지점에서 정사각형으로 이루어진 미로에 대한 지도를 발견하였다. 하지만 '문도'는 머리가 나빠서 프로그램 없이는 미로를 빠져나올 수가 없다. 입력으로 길에 대한 정보가 주어질 때 '문도'가 승규를 피해 가장 빠르게 도망가는 길의 길이를 찾아 알려주자.
 
이동은 상하좌우만 가능하다.

Input

첫 줄에 테스트 케이스의 수 T가 주어진다.  
 
각 테스트 케이스의 첫 번째 줄에는 정사각형의 한 면의 크기인 N(3 <= N <= 100)이 주어진다.  
두 번째 줄에는 N 줄 만큼 N x N의 정사각형 모양을 한 값이 들어온다.   
이때 ‘#’은 벽, ‘.’은 길, 'S'는 출발 지점, ‘E'는 도착 지점을 뜻한다.  
 
출발 지점은 한 곳만 존재할 수 있으며 도착 지점은 나오지 않거나 여러 곳이 나올 수 있다.  
S와 E가 같은 위치에 있을 수 없으며 지도의 주변은 벽으로 둘러싸여 있다고 가정한다.

Output

각 테스트 케이스 마다 ‘문도’가 가장 빨리 도망칠 수 있는 거리를 출력한다.  
 
이동 거리 1개 당 1m 이며 출력 결과는 아래의 Sample output과 같은 양식으로 처리한다.  
만약 모든 경우에서 E로 가는 길이 없다면 ‘문도’가 절규하는 용어인 “Mundo!!!” ( “ ” 제외)를 출력한다.

Sample Input

Sample Output

3
5
#E###
#...#
#...#
#...S
#####
3
E.#
##.
#S.
4
.E..
#.#E
..#.
.S..
6m
Mundo!!!
3m

Source

2013 Ajou Programming Contest