시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 262 164 145 68.075%

문제

N-퍼즐은 많은 다양한 형태와 이름이 있다. 이번 문제에서 우리가 살펴볼 것은 15-퍼즐이다.

15-퍼즐은 4*4보드에서 움직일 수 있는 정사각형으로 이루어져 있고, 한 정사각형은 빠져있다. 정사각형은 A부터 O까지 이름이 붙여져 있다. 이 퍼즐을 풀면 다음과 같은 그림이 된다.

A B C D
E F G H
I J K L
M N O .

우리는 이러한 15-퍼즐에서 흩어짐 정도를 계산할 수 있다. 흩어짐 정도는 각 정사각형의 현재 위치와 퍼즐을 풀었을 때의 위치와의 거리의 합이다.

두 정사각형의 거리는 그 두 정사각형 사이의 맨해튼 거리이다.

15-퍼즐이 주어졌을 때, 흩어짐 정도를 계산하는 프로그램을 작성하시오.

입력

4줄에 걸쳐 현재 퍼즐의 상태가 주어진다.

출력

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

예제 입력

ABCD
EFGH
IJKL
M.NO

예제 출력

2

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 2번