프로그램 명: coci_npuzzle
제한시간: 1 초

[요약] 아래는 최초 퍼즐의 위치이다.

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

섞은 후의 퍼즐 판이다.

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

배치한 후의 원래의 위치와의 거리(맨하탄 거리)의 차의 합을 구하는 문제이다.


그래서 답은 6

N-puzzle is a puzzle that goes by many names and has many variants.

In this problem we will use the 15-puzzle. It consists of a 4-by-4 grid of sliding squares where one square is missing. The squares are labeled with uppercase letters 'A' through 'O', with the desired layout as follows:

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

It can be useful (for example, when solving the puzzle using a computer) to define the "scatter" of a puzzle as the sum of distances between each square's current position and its position in the desired layout. The distance between two squares is their Manhattan distance (the absolute value of the sum of differences between the two rows and the two columns).

Write a program that calculates the scatter of the given puzzle.

입력

Four lines of input contain four characters each, representing the state of the puzzle.

출력

Output the scatter of the puzzle on a single line.

입출력 예

입력

ABCD 
EFGH 
IJKL 
M.NO 

출력

2 

입력

.BCD 
EAGH 
IJFL 
MNOK 

출력

6 

출처:coci/2006-2007/contest3 2
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]