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