1634: (알고리즘 설계) 낙하 하는 로봇
[만든사람 : 이건우 선생님]
문제 설명
로봇은 최단 경로를 찾을 때 까지 모든 경로를 탐색 하려고 한다. 로봇은 중력의 영향을 받기 때문에 아래에 블록이 없을 경우 블록이 있을 때 까지 아래로 떨어진다. 로봇은 다음과 같은 행동을 할 수 있다.
1. 오른쪽 이동
2. 왼쪽으로 이동
3. 오른쪽 점프 (위에 블록이 없고, 오른쪽에 블록이 있을 경우 -> 오른쪽 대각선 위 이동 가능)
4. 왼쪽 점프 (위에 블록이 없고, 왼쪽에 블록이 있을 경우 -> 왼쪽 대각선 위 이동 가능)
길을 표시하기 위해 최대 가로 20 세로 20의 정보를 입력할 수 있으며 입력한 정보의 바깥쪽 길은 무조건 블록으로 막혀 있다. 즉, 20X20의 내용을 입력하면 막혀 있는 블록 포함하면 22X22의 정보를 가지고 탐색한다.
로봇의 최소 이동 횟수를 구하는 프로그램을 작성해라!
(단, 중력에 의해 떨어지는 과정은 이동으로 취급하지 않는다.)
7번 만에 도착하는 예시
입력 설명
첫 줄에 정수 두 개가 입력이 된다. 이 두 정수는 가로, 세로의 칸의 개수다.
그 다음에 0은 빈 공간, 1은 벽, 2는 도착지점, 3은 시작 위치로 가정해 길을 표시한다.
출력 설명
최소 이동 횟수를 출력한다.
만일 길 찾기가 불가능할 경우 “실패” 만 출력한다.
입력 예시 Copy
8 3
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1
3 1 2 0 0 0 1 0
출력 예시 Copy
4