15-Puzzle Displacement

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:

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.

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

Print the puzzle's displacement on one line.