#2171 얼음동굴

1 s   128 MB  

Description

헌정이는 2014년 4월 5일에 있을 자신이 가장 좋아하는 가수 NULL의 컴백 콘서트를 예매했다. 하지만 현정이의 베스트 프랜드 중 한 명의 생일파티가 그 날로 정해져 버려서, 헌정이는 친구를 위하여 눈물을 머금고 콘서트를 포기하게 되었다. 콘서트 티켓을 양도하고 친구의 생일을 기다리던 헌정이는 어느 날, 청천벽력 같은 소리를 듣게 된다. 친구들의 변심으로 인해 약속 날짜를 옮기게 된 것이다.

이에 분노한 헌정이는 화를 못 이기고, 약속을 파토 나게 한 주범 4대 천왕을 찾아 혼내주기로 결심한다. 헌정이는 고향으로 가려면 중간에 미로같이 얽힌 얼음 동굴을 반드시 지나야만 한다. 오랜만에 고향에 가는 헌정이는 미로의 길을 잊어버리고 말았다! 동굴 안이라 통신도 되지 않는 상태에서 다행히 헌정이는 동굴의 구조가 그려진 지도를 발견한다.

지도의 예시(왼쪽)와, 최적의 탈출 경로(오른쪽)

                                                                                    <지도의 예시(왼쪽)와, 최적의 탈출 경로(오른쪽)> 

 

동굴 미로는 왼쪽의 그림처럼 N*N 크기의 정사각형 모양으로 되어있다. N*N 크기의 미로의 밖은 모두 바위로 둘러 쌓여 있으며, 미로의 중간 중간 바위로 막혀있는 곳이 있다. 정지한 상태의 헌정이는 상하좌우로 이동할 수 있다. 하지만 모든 바닥이 미끄러운 얼음이기에, 한번 움직이면 다시 바위에 부딪힐 때 까지 계속 그 방향으로 전진해야 한다. 바위에 부딪히면 다시 정지하여 상하좌우로 움직일 수 있다.

헌정이는 (1, 1)의 입구에서 출발하여 (N, N)의 출구에 도착해야 한다. 이미 먼 거리를 걸어온 헌정이는 너무 지쳐있기에, 최대한 적게 벽에 부딪히고 동굴을 탈출하고 싶다. N*N 크기의 지도가 주어질 때, 헌정이가 최소한으로 벽과 돌에 부딪히면서 목적지에 도착할 수 있는 방법을 찾아 주자.

Input

첫 번째 줄에는 테스트 케이스의 수 C(1 ≦ C ≦ 100)가 주어진다.
각 줄의 첫 번째 줄에는 동굴의 가로와 세로 크기인 N(1 ≦ N ≦ 30)이 주어진다. 2번째 줄부터 N+1번째 줄까지는 각 칸의 정보가 공백으로 구분되어 0과 1로 들어온다. 0은 비어있는 칸을 뜻하고, 1은 돌으로 막혀진 칸을 뜻한다. 단, 출발지와 목적지에는 돌이 존재하지 않는다. 하지만 목적지에 도착할 때에 부딪히는 횟수도 계산한다.

Output

각 테스트 케이스에 대하여, 한 줄에 답을 출력한다. 출발지에서부터 목적지까지 가는 답이 존재하는 경우, 헌정이가 목적지까지 도달하기 위해 최소로 부딪혀야 하는 횟수를 출력한다. 단, 목적지까지 가는 경로가 존재하지 않는 경우에는 “Beautiful Day”를 출력한다.

Sample Input

Sample Output

2
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
5
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
2
Beautiful Day

Source

2014 Ajou Programming Contest, Division 1 - 김동이 (mitslll, 아주대학교)