15-퍼즐 흩어짐 정도

15-퍼즐은 4행 4열 보드에 있는 움직일 수 있는 정사각형 타일 15개와 빈 칸 하나로 이루어진 퍼즐이다. 타일에는 A부터 O까지 이름이 붙어 있다.

퍼즐이 풀린 상태는 다음과 같다.

각 타일의 현재 위치와 풀린 상태에서의 위치 사이의 맨해튼 거리를 모두 더한 값을 이 퍼즐의 흩어짐 정도라고 하자. 빈 칸 .은 계산에 포함하지 않는다.

주어진 15-퍼즐의 흩어짐 정도를 계산하라.

4줄에 걸쳐 현재 퍼즐의 상태가 주어진다. 각 줄은 보드의 한 행을 나타낸다.

퍼즐의 흩어짐 정도를 한 줄에 출력한다.