문제 번호 3549 -- 미로 찾기

3549: 미로 찾기

시간제한: 1 Sec  메모리제한: 128 MB
제출: 54  푼문제: 5
[제출][채점상황][게시판]

문제설명

로봇공학자를 꿈꾸는 홍만이는 미로 안에서 길을 찾아 도착 지점으로 가는 로봇을 설계하려고 한다.

이 로봇은 바라보는 방향으로 길을 따라 동서남북 가운데 하나의 방향으로 움직이며, 로봇의 동작은 다음과 같이 세 가지이다.

동작1: 전진n(현재 향하고 있는 방향으로 n칸만큼 움직인다.)

동작2: 좌회전 (왼쪽으로 90o 회전한다.)

동작33: 우회전 (오른쪽으로 90o 회전한다.)

미로의 상태는 갈 수 있는 지점은0, 갈 수 없는 지점은 1로 지정하여 직사각형 모양으로 로봇에게 입력된다.

로봇의 현재 위치와 바라보는 방향 및 도착 지점이 주어졌을 때, 로봇이 도착 지점으로 이동하는데 필요한 동작의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫 행에는 미로의 행의 개수 m과 열의 개수 n이 빈 칸으로 구분되어 주어진다. (단, m ,n은 20이하의 자연수)

둘째 행부터 m+1행까지 미로의 상태가 빈 칸으로 구분되어 주어진다.

m+2행에는 현재 위치(행, 열)와 바라보는 방향(동1, 서2, 남3, 북4)이 빈 칸으로 구분되어 주어진다.

m+3행에는 도착 지점(행, 열)이 빈 칸으로 구분되어 주어진다.

출력

첫 행에는 동작의 최소 횟수를 출력한다.

입력예시

5 5
0 0 0 0 0 
0 1 0 1 0 
0 0 0 1 0 
1 0 0 1 0 
0 0 0 0 0 
4 3 3
2 5

출력예시

5

도움말



출처

[제출][채점상황]