AT_past19_o.15パズル

称一个 $4\times 4$ 的网格为好网格，当且仅当满足以下条件：

对于每个 $1$ 到 $15$ 之间的整数（包含 $1$ 和 $15$），网格中恰好有一个格子写有该整数。
剩下的唯一一个格子没有写任何数。换句话说，恰好有且只有一个格子为空。

现给定两个不同的好网格 $S$ 和 $T$。
这里，好网格 $S$ 由 $16$ 个整数 $S_{i,j}$（$1\leq i,j\leq 4$）给出。
如果 $1\leq S_{i,j}\leq 15$，则表示第 $i$ 行第 $j$ 列的格子上写着 $S_{i,j}$；
如果 $S_{i,j}=-1$，则表示第 $i$ 行第 $j$ 列的格子为空。
同理，$T$ 也由 $16$ 个整数 $T_{i,j}$（$1\leq i,j\leq 4$）给出。

你需要计算，从 $S$ 经过若干次如下操作，最少多少步能够变成 $T$。
如果用 $30$ 次操作及以内（包括 $30$ 次）无法变为 $T$（包括任意次数都无法变为 $T$ 的情形），则输出 $-1$。

• 选择一个与空格相邻的格子，将该格子上的数移动到空格中，然后该格子变为空。

输入为一行，从标准输入读取，格式如下：

$S_{1,1}\ S_{1,2}\ S_{1,3}\ S_{1,4}\ S_{2,1}\ S_{2,2}\ S_{2,3}\ S_{2,4}\ S_{3,1}\ S_{3,2}\ S_{3,3}\ S_{3,4}\ S_{4,1}\ S_{4,2}\ S_{4,3}\ S_{4,4}\ T_{1,1}\ T_{1,2}\ T_{1,3}\ T_{1,4}\ T_{2,1}\ T_{2,2}\ T_{2,3}\ T_{2,4}\ T_{3,1}\ T_{3,2}\ T_{3,3}\ T_{3,4}\ T_{4,1}\ T_{4,2}\ T_{4,3}\ T_{4,4}$

输出最少的操作次数，使得网格由 $S$ 变为 $T$。
如果用 $30$ 次操作以内无法变为 $T$，请输出 $-1$。

样例解释 1

记 $(i,j)$ 表示网格中第 $i$ 行第 $j$ 列的格子。
在 $S$ 中，空格位于 $(4,4)$。
可以通过以下三步操作将 $S$ 变为 $T$：

• 选择 $(3,4)$，将 $12$ 移动到 $(4,4)$，$(3,4)$ 变为空；
• 选择 $(3,3)$，将 $11$ 移动到 $(3,4)$，$(3,3)$ 变为空；
• 选择 $(2,3)$，将 $7$ 移动到 $(3,3)$，$(2,3)$ 变为空。

另一方面，不能用两步或更少变为 $T$，因此输出 $3$。

样例解释 2

无法在 $30$ 步以内变为 $T$，所以输出 $-1$。

数据范围

• $-1\leq S_{i,j},T_{i,j}\leq 15$
• $S_{i,j},T_{i,j}\neq 0$
• $S$ 和 $T$ 均为不同的好网格。
• 所有输入均为整数。

由 ChatGPT 5 翻译