로봇

많은 공장에서는 로봇이 정해진 궤도를 따라 움직인다. 이 공장의 로봇은 항상 동, 서, 남, 북 중 한 방향을 바라보며, 바라보는 방향으로만 전진할 수 있다. 로봇을 제어하는 명령은 다음 두 종류이다.

• 명령 1. Go k: k는 1, 2, 3 중 하나이다. 로봇이 현재 바라보는 방향으로 k칸 전진한다.
• 명령 2. Turn dir: dir은 left 또는 right이다. 각각 왼쪽 또는 오른쪽으로 90도 회전한다.

공장 안의 궤도 상태는 0과 1로 이루어진 직사각형 격자로 주어진다. 0은 궤도가 있어 로봇이 이동할 수 있는 칸이고, 1은 궤도가 없어 이동할 수 없는 칸이다. 로봇이 한 번에 여러 칸을 전진하려면 지나가는 모든 칸에 궤도가 있어야 한다.

아래 그림은 로봇이 (4, 2)에서 남쪽을 바라보고 있을 때, (2, 4)에서 동쪽을 바라보도록 이동하는 한 상황을 보여 준다. 이 경우에는 9번의 명령으로 이동할 수 있다.

로봇의 현재 위치와 방향, 그리고 목표 위치와 방향이 주어질 때, 목표 상태에 도달하기 위해 필요한 최소 명령 횟수를 구하시오.

첫째 줄에 공장 격자의 세로 길이 M과 가로 길이 N이 공백으로 구분되어 주어진다. M과 N은 모두 100 이하의 자연수이다.

다음 M개 줄에는 각 줄마다 N개의 정수가 공백으로 구분되어 주어진다. 각 값은 0 또는 1이며, 0은 로봇이 이동할 수 있는 칸, 1은 이동할 수 없는 칸을 뜻한다.

그다음 줄에는 로봇의 출발 위치의 행 번호, 열 번호, 바라보는 방향이 공백으로 구분되어 주어진다. 마지막 줄에는 목표 위치의 행 번호, 열 번호, 바라보는 방향이 같은 형식으로 주어진다.

방향은 동쪽 1, 서쪽 2, 남쪽 3, 북쪽 4로 주어진다. 출발 상태에서 목표 상태까지는 항상 도달할 수 있다.

로봇을 목표 위치와 방향으로 만들기 위해 필요한 최소 명령 횟수를 첫째 줄에 출력한다.