전진 우회전 좌회전 네비게이션 timer 2s memory 512MB

N \times N 격자판이 있는데, 가장 좌측 하단(A[N][1])에 있는 칸에 위치한 사람은 처음에 우측을 보거나 위를 보는 방향으로 서있다.

사람은 "전진", "우회전", "좌회전" 중 하나의 선택을 하여 이동을 하는데, 장애물이 있거나 격자판을 벗어나는 방향으로는 이동이 불가능하다.

"전진 우회전 좌회전 네비게이션"은 처음 사람이 우측을 보는지 위를 보는지 알지 못하기에 두 경우를 통틀어 처음에 어느 방향으로 서 있었는지는 별개로 가장 우측 상단의 칸(A[1][N])에 가장 빨리 도착하기 위해 이동해야하는 순서를 알려준다.

• 경로A를 따라 갔을 때, 처음 우측을 보고 있었다면 5초만에 가고, 위를 보고 있었다면 10초만에 가는 경로라면 경로A는 10초만에 가는 것이 보장된 경로이다.

• 경로B를 따라 갔을 때, 처음 우측을 보고 있었다면 8초만에 가고, 위를 보고 있었다면 9초만에 가는 경로라면 경로B는 9초만에 가는 것이 보장된 경로이다.

• 이 경우, 경로B가 경로A보다 더 빠르게 도착하도록 알려주는 경로이다.

이런 네비게이션을 이용한다면 목적지에 몇 번의 이동을 통해 도착하는 것이 가능한지 출력하는 프로그램을 작성하시오.