통나무 옮기기

시간 제한

2초

메모리 제한

128 MB

문제

가로와 세로의 길이가 같은 평지에서 벌목 작업을 한다. 평지는 문자로 표현되며, 0은 빈칸, 1은 아직 잘리지 않은 나무, B는 통나무의 처음 위치, E는 통나무를 옮겨야 하는 최종 위치를 뜻한다.

다음과 같은 지형이 주어질 수 있다.

통나무는 항상 길이가 3이며, 세 칸이 한 행 또는 한 열에 연속해서 놓인다. 처음 위치의 세 칸은 B, 최종 위치의 세 칸은 E로 주어진다. 통나무는 다음 다섯 가지 기본 동작만 할 수 있다.

코드	의미
`U`	통나무를 위로 한 칸 옮긴다.
`D`	통나무를 아래로 한 칸 옮긴다.
`L`	통나무를 왼쪽으로 한 칸 옮긴다.
`R`	통나무를 오른쪽으로 한 칸 옮긴다.
`T`	중심 칸을 기준으로 90도 회전한다.

통나무를 상하좌우로 옮길 때에는 이동한 뒤 통나무가 차지하는 세 칸이 모두 평지 안에 있어야 하고, 그 칸들에 1이 없어야 한다. 통나무는 한 번에 한 칸만 움직이며, 움직이는 중에도 항상 한 행 또는 한 열에 놓여 있어야 한다.

회전은 통나무의 가운데 칸을 중심으로만 할 수 있다. 길이가 3이므로 가운데 칸은 항상 존재한다. 회전하려면 가운데 칸을 둘러싼 3 x 3 정사각형 전체가 평지 안에 있어야 하고, 그 9칸 어디에도 1이 없어야 한다. 아래 그림처럼 물음표로 표시되는 주변 칸도 모두 비어 있어야 한다.

가로 통나무를 회전할 때 필요한 공간:

세로 통나무를 회전할 때 필요한 공간:

처음 위치에서 최종 위치까지 통나무를 옮기는 데 필요한 기본 동작의 최소 횟수를 구하시오.

입력

첫째 줄에 평지 한 변의 길이 N이 주어진다. (4 <= N <= 50)

다음 N개의 줄에는 지형 정보가 주어진다. 각 줄은 길이가 N인 문자열이며, 문자 사이에 공백은 없다. 문자열은 0, 1, B, E로만 이루어진다.

처음 위치를 나타내는 B는 정확히 세 개이고, 최종 위치를 나타내는 E도 정확히 세 개이다. 각각의 세 칸은 한 행 또는 한 열에 연속해서 놓인다.

출력

처음 위치에서 최종 위치까지 통나무를 옮기는 데 필요한 최소 동작 횟수를 출력한다.

옮길 수 없다면 0을 출력한다.