많은 공장에서 로봇이 이용되고 있다.

우리 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며 움직이는 방향은 동, 서, 남, 북 가운데 하나이다.

로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

*명령 1. Go k - k 는 1 또는 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k 칸만큼 움직인다.

*명령 2. Turn dir - dir 은 left 또는 right 이며 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다.

0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고 1은 궤도가 없어 로봇이 갈 수 없는 지점이다.

로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때

이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때 로봇을 원하는 위치로 이동시키고 원하는 방향으로 바라보도록 하는데

최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

로봇 timer 1s memory 64MB

로봇 1s 64MB