컬링 2.0

MM-21 행성에서는 올해 올림픽 이후 컬링이 인기를 끌고 있지만, 규칙은 우리의 것과 조금 다릅니다. 경기는 정사각형 격자가 그려진 얼음판 위에서 진행되며, 돌은 단 하나만 사용합니다. 목표는 돌을 출발 칸에서 도착 칸까지 최소 던지기 횟수로 이동시키는 것입니다.

판의 일부 칸은 블록으로 막혀 있습니다. 출발 칸과 도착 칸이라는 두 특수한 칸은 절대 블록으로 막혀 있지 않으며, 서로 다른 칸입니다. 돌은 한번 움직이기 시작하면 블록에 부딪힐 때까지 계속 나아갑니다. 돌을 도착 칸으로 유도하려면 블록에 부딪혀 멈춘 뒤 다시 던져야 할 수도 있습니다.

그림 D-1: 판의 예시 (S: 출발, G: 도착)

돌은 다음 규칙에 따라 움직입니다.

• 처음에 돌은 출발 칸에 정지해 있습니다.
• 돌은 x축 또는 y축 방향으로만 움직일 수 있습니다. 대각선 이동은 허용되지 않습니다.
• 돌이 정지해 있을 때 던져서 움직이게 할 수 있습니다. 던지려는 방향의 바로 옆 칸이 블록으로 막혀 있지 않은 한 어느 방향으로든 던질 수 있습니다.
• 한번 던져진 돌은 다음 중 하나가 일어날 때까지 같은 방향으로 계속 움직입니다.
  • 블록에 부딪힙니다. 돌은 그 블록 바로 앞 칸에 멈추고, 그 블록은 사라집니다.
  • 판 밖으로 나갑니다. 게임은 실패로 끝납니다.
  • 도착 칸에 도달합니다. 돌은 그 자리에 멈추고 게임은 성공으로 끝납니다.
• 한 게임에서 돌은 최대 10번까지만 던질 수 있습니다. 10번 안에 도착 칸에 이르지 못하면 게임은 실패로 끝납니다.

그림 D-2: 돌의 움직임

이 규칙에 따라, 돌이 출발 칸에서 도착 칸까지 갈 수 있는지, 갈 수 있다면 필요한 최소 던지기 횟수를 구하십시오. 예시 판에서는 4번의 던지기가 필요하며, 도중에 블록이 부서지면서 판의 배치가 바뀐다는 점에 유의하십시오.

그림 D-3: 예시 판에 대한 해답과 그 결과 배치

입력은 여러 개의 데이터셋으로 이루어집니다. 입력의 끝은 공백으로 구분된 두 개의 0으로 이루어진 줄로 표시됩니다. 데이터셋의 개수는 100을 넘지 않습니다.

각 데이터셋의 형식은 다음과 같습니다.

w h
1번째 줄
...
h번째 줄

첫 줄에는 판의 너비 $w$와 높이 $h$가 주어지며, $2 \le w \le 20$, $1 \le h \le 20$을 만족합니다. 이어지는 $h$개의 줄에는 각각 공백으로 구분된 $w$개의 정수가 주어져 판의 한 줄을 나타냅니다. 각 정수는 해당 칸의 상태를 의미합니다.

각 데이터셋에 대해, 출발 칸에서 도착 칸까지 이동하는 데 필요한 최소 던지기 횟수를 한 줄에 출력하십시오. 그러한 경로가 없으면 대신 -1을 출력하십시오. 그 줄에는 이 숫자 외에 다른 문자가 있어서는 안 됩니다.