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$ 所需操作次数的最小值。

输入输出样例 #1

输入 #1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
1 3 2 5 4
11 13 12 15 14
6 8 7 10 9
16 18 17 20 19

输出 #1

3

输入输出样例 #2

输入 #2

2 2
1 1
1 1
1 1
1 1000000000

输出 #2

-1

输入输出样例 #3

输入 #3

3 3
8 1 6
3 5 7
4 9 2
8 1 6
3 5 7
4 9 2

输出 #3

0

输入输出样例 #4

输入 #4

5 5
710511029 136397527 763027379 644706927 447672230
979861204 57882493 442931589 951053644 152300688
43971370 126515475 962139996 541282303 834022578
312523039 506696497 664922712 414720753 304621362
325269832 191410838 286751784 732741849 806602693
806602693 732741849 286751784 191410838 325269832
304621362 414720753 664922712 506696497 312523039
834022578 541282303 962139996 126515475 43971370
152300688 951053644 442931589 57882493 979861204
447672230 644706927 763027379 136397527 710511029

输出 #4

20

说明/提示

限制条件

• 输入的所有值均为整数。
• $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 翻译