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

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

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

경로A를 따라 갔을 때, 처음 우측을 보고 있었다면 5초만에 가고, 위를 보고 있었다면 10초만에 가는 경로라면 경로A는 10초만에 가는 것이 보장된 경로이다.
경로B를 따라 갔을 때, 처음 우측을 보고 있었다면 8초만에 가고, 위를 보고 있었다면 9초만에 가는 경로라면 경로B는 9초만에 가는 것이 보장된 경로이다.
이 경우, 경로B가 경로A보다 더 빠르게 도착하도록 알려주는 경로이다.

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

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

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