P1225 Black-and-White Chess Game

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.

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 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)$.

SPJ provided by @zhouyonglong. Translated by ChatGPT 5