로봇

로봇 이동 연구소(Robot Moving Institute)는 매장에서 물건을 옮기기 위해 로봇 한 대를 사용한다. 로봇은 한 지점에서 다른 지점으로 이동할 때 걸리는 시간을 최소로 해야 한다.

로봇은 직선 궤도(트랙) 위에서만 움직인다. 모든 트랙은 직사각형 격자를 이루며, 이웃한 트랙 사이의 간격은 1미터이다. 매장은 가로 $N$, 세로 $M$ 미터의 직사각형이고 이 격자로 완전히 덮여 있다. 매장 벽에 가장 가까운 트랙은 벽에서 정확히 1미터 떨어져 있다.

로봇은 지름이 1.6미터인 원 모양이며, 트랙이 로봇의 중심을 지난다. 로봇은 항상 북·남·동·서 중 한 방향을 바라보고, 트랙은 남북 방향과 동서 방향으로 놓여 있다. 로봇은 자신이 바라보는 방향으로만 움직일 수 있으며, 바라보는 방향은 각 트랙 교차점에서 바꿀 수 있다. 처음에 로봇은 어떤 교차점에 서 있다.

매장의 장애물은 바닥에서 $1\text{m} \times 1\text{m}$ 크기의 칸을 차지하며, 각 장애물은 트랙으로 둘러싸인 한 칸 안에 들어 있다.

로봇은 두 가지 명령으로 제어된다.

• GO 명령은 정수 매개변수 $n \in \{1, 2, 3\}$ 을 가진다. 이 명령을 받으면 로봇은 바라보는 방향으로 $n$ 미터 이동한다.
• TURN 명령은 left 또는 right 매개변수를 가진다. 이 명령을 받으면 로봇은 지정된 방향으로 방향을 90° 회전한다.

각 명령을 실행하는 데 1초가 걸린다.

주어진 출발점에서 도착점까지 로봇이 이동하는 데 걸리는 최소 시간을 구하는 프로그램을 작성하라.

입력은 여러 블록으로 이루어진다. 각 블록의 첫 줄에는 두 정수 $M \le 50$ 과 $N \le 50$ 이 공백 하나로 구분되어 주어진다. 이어지는 $M$ 개의 줄에는 각각 $N$ 개의 수(0 또는 1)가 공백으로 구분되어 주어진다. 1은 장애물, 0은 빈 칸을 뜻한다. (트랙은 칸과 칸 사이에 있다.)

블록의 마지막 줄에는 네 개의 양의 정수 $B_1$ $B_2$ $E_1$ $E_2$ 가 각각 뒤에 공백 하나를 두고 주어진 뒤, 출발 시점의 로봇 방향을 나타내는 단어가 온다. $B_1, B_2$ 는 로봇이 놓인 출발 칸의 좌표로, 로봇은 그 칸의 북서쪽 모서리(교차점)에 놓인다. $E_1, E_2$ 는 로봇이 도착해야 하는 칸의 좌표이며, 로봇은 그 칸의 북서쪽 모서리에 도착해야 한다. 도착 시점의 방향은 정해져 있지 않다.

좌표는 (행, 열) 형식이다. 즉 가장 북서쪽 칸의 좌표는 (0, 0)이고, 가장 남동쪽 칸의 좌표는 $(M-1, N-1)$ 이다. 방향은 north, west, south, east 중 하나로 주어진다.

마지막 블록은 $M = 0$, $N = 0$ 인 한 줄만으로 이루어진다.

마지막 블록을 제외한 각 블록마다 한 줄씩 출력한다. 출력 줄의 순서는 입력 블록의 순서와 같다. 각 줄에는 로봇이 출발점에서 도착점까지 도달하는 데 필요한 최소 초를 출력한다. 출발점에서 도착점으로 가는 경로가 존재하지 않으면 그 줄에는 -1을 출력한다.