P2324 [SCOI2005] Knight's Spirit

On a $5 \times 5$ board there are $12$ white knights and $12$ black knights, plus one empty cell. At any time, a knight may move into the empty cell following the knight's move (it can move to a cell where the x-coordinate differs by $1$ and the y-coordinate differs by $2$, or the x-coordinate differs by $2$ and the y-coordinate differs by $1$). Given an initial board, how can it be transformed, via moves, into the following target board:  To embody the "knight's spirit", they must finish in the minimal number of moves.

The first line contains a positive integer $T$ ($T \le 10$), indicating there are $T$ test cases. Then follow $T$ matrices of size $5 \times 5$, where `0` denotes a white knight, `1` denotes a black knight, and `*` denotes the empty cell. There is no blank line between two test cases.

For each test case, output one line. If the target state can be reached within $15$ moves (inclusive), output the minimal number of moves; otherwise, output `-1`.

 Translated by ChatGPT 5