N-puzzle

\(N\)-퍼즐은 여러 이름으로 불리며 다양한 변형이 있는 퍼즐이다. 이 문제에서는 \(15\)-퍼즐을 사용한다. 이 퍼즐은 미끄러지는 정사각형 조각들의 \(4\) × \(4\) 격자로 이루어져 있는데, 조각 하나가 비어 있다. 조각들에는 대문자 A부터 O까지가 적혀 있으며, 목표 배치는 다음과 같다:

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

퍼즐의 흩어짐(scatter)을 각 조각의 현재 위치와 목표 배치에서의 위치 사이 거리의 합으로 정의하면 (예를 들어 컴퓨터로 퍼즐을 풀 때) 유용할 수 있다. 두 조각 사이의 거리는 맨해튼 거리(두 행의 차와 두 열의 차의 절댓값의 합)이다.

네 줄에 걸쳐 각각 네 문자가 주어진다. 퍼즐의 상태를 나타낸다.

퍼즐의 흩어짐을 한 줄에 출력한다.

riseoj 작성

출처 COCI 2006/2007 Contest 3