Description

In a $4 \times 4$ grid, several identical toys are placed. Someone wants to rearrange these toys into his ideal state. Each move can only shift a toy up, down, left, or right, and the destination position must be empty. Please transform the initial state into the target state using the fewest number of moves.

Input Format

The first four lines describe the initial state of the toys, each line containing four numbers $1$ or $0$. Here, $1$ means a toy is placed in the cell, and $0$ means the cell is empty. Then there is a blank line. The next four lines describe the target state, each line containing four numbers $1$ or $0$, with the same meaning as above.

Output Format

Output a single integer: the minimum number of moves required.

1111
0000
1110
0010 

1010
0101
1010
0101

4

Hint

Translated by ChatGPT 5