Toy Relocation Puzzle

You are given a 4×4 grid where several identical toys are placed. You are also provided with a target configuration representing the desired relocation of the toys. In each move, you can select a toy and move it one cell horizontally or vertically (up, down, left, or right) to an adjacent empty cell (i.e. a cell without a toy). The goal is to transform the initial configuration into the target configuration with the minimum number of moves. Note that the toys are identical, so you only need to match the sets of positions. If it is impossible to reach the target configuration, output -1.

The positions on the grid are indexed by rows and columns (0-indexed). An input cell containing a 1 indicates that there is a toy in that cell, while a 0 represents an empty cell.

Formally, if we represent a configuration as a binary matrix \(A\) of size 4×4, a move consists of selecting a cell \((i,j)\) with \(A_{i,j}=1\) and an adjacent cell \((i+\delta_i,j+\delta_j)\) with \(A_{i+\delta_i,j+\delta_j}=0\) (with \(\delta\) being one of \((-1,0)\), \((1,0)\), \((0,-1)\), \((0,1)\)). The moved state is obtained by setting \(A_{i,j}=0\) and \(A_{i+\delta_i,j+\delta_j}=1\). The task is to find the minimum number of moves to transform the initial configuration into the target configuration.

Any formulas appearing in the description are formatted in \(\LaTeX\) format.

inputFormat

The input consists of 8 lines:

• The first 4 lines describe the initial configuration of the grid. Each of these lines contains 4 space-separated numbers (each either 0 or 1).
• The next 4 lines describe the target configuration in the same format.

outputFormat

Output a single integer which is the minimum number of moves required to reach the target configuration from the initial configuration. If it is impossible, output -1.

sample

1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0

1