Description

The board of the black-and-white chess game consists of a $4 \times 4$ grid. Each square contains $1$ piece, with $8$ white pieces and $8$ black pieces in total. Every arrangement of these $16$ pieces constitutes a game state. Two squares that share a common edge are called adjacent squares. A square can have at most $4$ adjacent squares. In each move, you may swap the pieces in any two adjacent squares. Given an initial game state and a target game state, write a program to compute the shortest sequence of moves that transforms the initial state into the target state.

Input Format

The input consists of $8$ lines. The first $4$ lines describe the initial game state, and the last $4$ lines describe the target game state. Each line contains $4$ numbers indicating the colors of the pieces in that row. "0" denotes a white piece; "1" denotes a black piece.

Output Format

Output the number of moves $n$ on the first line. Then output $n$ lines, each containing $4$ numbers that represent the positions of the two adjacent squares whose pieces are swapped in that move. For example, abcd denotes swapping the piece at $(a,b)$ with the piece at $(c,d)$.

1111
0000
1110
0010
1010
0101
1010
0101

4
1222
1424
3242
4344

Hint

SPJ provided by @zhouyonglong.

Translated by ChatGPT 5