15-Puzzle Displacement

Interview

Time limit1sMemory limit128 MB

Summary

Compute the total Manhattan distance of each labeled tile from its position in the solved 4x4 15-puzzle board.

Level: Easy2 of 10
Topics: Array, Math, Implementation
Solved: No attempts yet

Problem

A 15-puzzle consists of fifteen movable square tiles on a 4 by 4 board and one empty cell. The tiles are labeled A through O.

The solved board is:


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

Define the puzzle's displacement as the sum, over all tiles, of the Manhattan distance between the tile's current position and its position in the solved board. The empty cell . is not included.

Given a 15-puzzle state, compute its displacement.

Input

The current puzzle state is given over 4 lines. Each line represents one row of the board.

Output

Print the puzzle's displacement on one line.

Examples2

Example 1
Input
```
ABCD
EFGH
IJKL
M.NO
```
Expected output
```
2
```
Example 2
Input
```
.BCD
EAGH
IJFL
MNOK
```
Expected output
```
6
```