[SCOI2005]骑士精神

在一个 $5\times 5$ 的棋盘上，有 $12$ 个白色骑士、 $12$ 个黑色骑士和一个空位。每次可以选择一个骑士，按照骑士的走法移动到空位：移动前后两个格子的横坐标之差与纵坐标之差分别为 $1$ 和 $2$ ，或分别为 $2$ 和 $1$ 。

给定一个初始棋盘，需要通过若干次移动，将其变为以下目标棋盘：

为了体现骑士精神，你需要使用最少的移动步数完成任务。

输入格式

第一行输入一个正整数 $T$ ，表示数据组数。

接下来输入 $T$ 个 $5\times 5$ 的字符矩阵。其中，字符 $0$ 表示白色骑士，字符 $1$ 表示黑色骑士，字符 $\ast$ 表示空位。相邻两组数据之间没有空行。

对于每组数据输出一行。

如果能在 $15$ 步以内（包括 $15$ 步）到达目标状态，则输出最少移动步数；否则输出 $-1$ 。

7
-1

本题为 SCOI 2005 试题「骑士精神」，题面与测试数据整理自 BZOJ。

7
-1