매직 스퀘어 돌리기

크기가 같은 여덟 개의 정사각형으로 이루어진 매직 스퀘어가 있다. 각 칸에는 서로 다른 색이 칠해져 있고, 색은 1부터 8까지의 자연수로 나타낸다.

상태는 왼쪽 위 칸에서 시작해 시계 방향으로 읽은 8개의 수열로 나타낸다. 위치 번호는 다음과 같다.

1 2 3 4
8 7 6 5

초기 상태는 (1, 2, 3, 4, 5, 6, 7, 8)이다. 어떤 상태에도 다음 네 가지 변환을 적용할 수 있다.

• A: 윗줄과 아랫줄 전체를 서로 바꾼다.
• B: 두 줄을 각각 오른쪽으로 한 칸 옮긴다. 각 줄의 맨 오른쪽 수는 그 줄의 맨 왼쪽으로 이동한다.
• C: 가운데 네 칸의 수를 반시계 방향으로 한 번 돌린다.
• D: 위치 1과 위치 5의 수를 서로 바꾼다.

초기 상태에서 시작해 주어진 목표 상태를 만들기 위해 필요한 최소 변환 횟수를 구하라. 목표 상태를 만들 수 없는 경우는 없다.

첫째 줄에 목표 상태를 나타내는 8개의 정수가 주어진다. 정수의 순서는 위에서 정의한 상태 수열의 순서이다.

첫째 줄에 필요한 최소 변환 횟수 L을 출력한다.