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 翻译