AT_abc332_d [ABC332D] Swapping Puzzle

给定两个 $H$ 行 $W$ 列的网格 $A$ 和 $B$。 对于满足 $1 \leq i \leq H$ 和 $1 \leq j \leq W$ 的每一组整数 $(i, j)$，我们称第 $i$ 行第 $j$ 列的格子为格子 $(i, j)$。网格 $A$ 的格子 $(i, j)$ 上写有整数 $A_{i, j}$，网格 $B$ 的格子 $(i, j)$ 上写有整数 $B_{i, j}$。 你可以重复任意多次（也可以一次都不做）以下两种操作中的任意一种： - 选择满足 $1 \leq i \leq H-1$ 的整数 $i$，交换网格 $A$ 的第 $i$ 行和第 $i+1$ 行。 - 选择满足 $1 \leq i \leq W-1$ 的整数 $i$，交换网格 $A$ 的第 $i$ 列和第 $i+1$ 列。 请判断通过上述操作的若干次重复，是否可以将网格 $A$ 变为网格 $B$。如果可以，请输出所需操作次数的最小值。 这里，网格 $A$ 和网格 $B$ 相等，指的是对于所有满足 $1 \leq i \leq H$ 和 $1 \leq j \leq W$ 的整数对 $(i, j)$，网格 $A$ 的格子 $(i, j)$ 和网格 $B$ 的格子 $(i, j)$ 上的整数都相等。

输入按以下格式从标准输入给出。 > $H$ $W$ > $A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$ > $A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$ > $\vdots$ > $A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$ > $B_{1, 1}$ $B_{1, 2}$ $\cdots$ $B_{1, W}$ > $B_{2, 1}$ $B_{2, 2}$ $\cdots$ $B_{2, W}$ > $\vdots$ > $B_{H, 1}$ $B_{H, 2}$ $\cdots$ $B_{H, W}$

如果无法将网格 $A$ 变为网格 $B$，输出 `-1`；如果可以，请输出将网格 $A$ 变为网格 $B$ 所需操作次数的最小值。

## 限制条件 - 输入的所有值均为整数。 - $2 \leq H, W \leq 5$ - $1 \leq A_{i, j}, B_{i, j} \leq 10^9$ ## 样例解释 1 将初始状态下网格 $A$ 的第 $4$ 列和第 $5$ 列交换后，网格 $A$ 变为如下所示： ``` 1 2 3 5 4 6 7 8 10 9 11 12 13 15 14 16 17 18 20 19 ``` 接着，将网格 $A$ 的第 $2$ 行和第 $3$ 行交换后，网格 $A$ 变为如下所示： ``` 1 2 3 5 4 11 12 13 15 14 6 7 8 10 9 16 17 18 20 19 ``` 最后，将网格 $A$ 的第 $2$ 列和第 $3$ 列交换后，网格 $A$ 变为如下所示，与网格 $B$ 完全一致： ``` 1 3 2 5 4 11 13 12 15 14 6 8 7 10 9 16 18 17 20 19 ``` 通过上述 $3$ 次操作可以将网格 $A$ 变为网格 $B$，且无法用更少的操作完成，因此输出 $3$。 ## 样例解释 2 无论如何操作，都无法将网格 $A$ 变为网格 $B$，因此输出 `-1`。 ## 样例解释 3 网格 $A$ 一开始就与网格 $B$ 完全一致。 由 ChatGPT 4.1 翻译