통나무옮기기 timer 1초 memory 64MB

가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고, 0은 아무것도 없음을 나타낸다. 다음과 같은 지형을 보자.

 

 

위의 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 하는 문제를 생각해 보자. BBB와 EEE의 위치는 임의로 주어진다. 단 문제에서 통나무의 길이는 항상 홀수이다. 즉 B의 개수는 항상 홀수(3, 5, 7, ...)이며 통나무는 한 행이나 한 열에 놓여있다. 또한 B의 개수와 E의 개수는 같다.

통나무를 움직이는 방법은 아래와 같이 상하좌우(Up, Down, Left, Right)와 회전(Turn)이 있다.

 

 

예를 들면, 다음과 같다.

 

이와 같은 방식으로 이동시킬 때에 그 움직일 위치에 다른 나무, 즉 1이 없어야만 움직일 수 있다. 그리고 움직임은 위의 그림과 같이 한 번에 한 칸씩만 움직인다. 단 움직이는 통나무는 어떤 경우이든지 중간단계에서 한 행이나 한 열에만 놓일 수 있다. 예를 들면 아래 그림에서 a와 같은 단계는 불가능한다. 그리고 회전의 경우에서는 반드시 중심점을 중심으로 90도 회전을 해야 한다.(항상 통나무의 길이가 홀수이므로 중심점이 있음에 유의하라.)

그리고 이런 회전(Turn)이 가능하기 위해서는 그 통나무를 둘러싸고 있는 정사각형의 구역에 단 한 그루의 나무도 없어야만 한다. 즉, 아래그림 b, d와 같이 ?로 표시된 지역에 다른 나무, 즉 1이 없어야만 회전시킬 수 있다. 따라서 c와 같은 경우에, 통나무는 왼쪽의 아직 벌목되지 않은 나무 때문에 회전시킬 수 없다.

 

문제는 통나무를 5개의 기본동작(U, D, L, R, T)만을 사용하여 처음위치(BBB...B)에서 최종위치(EEE...E)로 옮기는 프로그램을 작성하는 것이다. 최소 횟수의 단위 동작을 사용하면 만점을 받고, 그렇지 않은 경우 회수가 많을수록 낮은 점수를 받는다.

주어지는 구역의 크기는 최대 50x50을 넘지 않는다. 통나무의 최대길이는 20을 넘지 않는다. 만일 동작이 불가능한 경우인데도 불구하고 옮기는 작업을 하게 되면 0점 처리된다.