15-퍼즐 흩어짐 정도
면접 대비시간 제한1초메모리 제한128 MB
4x4 15퍼즐에서 각 타일이 정답 위치와 떨어진 맨해튼 거리의 합을 계산합니다.
문제
15-퍼즐은 4행 4열 보드에 있는 움직일 수 있는 정사각형 타일 15개와 빈 칸 하나로 이루어진 퍼즐이다. 타일에는 A부터 O까지 이름이 붙어 있다.
퍼즐이 풀린 상태는 다음과 같다.
각 타일의 현재 위치와 풀린 상태에서의 위치 사이의 맨해튼 거리를 모두 더한 값을 이 퍼즐의 흩어짐 정도라고 하자. 빈 칸 .은 계산에 포함하지 않는다.
주어진 15-퍼즐의 흩어짐 정도를 계산하라.
입력
4줄에 걸쳐 현재 퍼즐의 상태가 주어진다. 각 줄은 보드의 한 행을 나타낸다.
출력
퍼즐의 흩어짐 정도를 한 줄에 출력한다.