交换拼图

题目描述

给定两个各有 $H$ 行 $W$ 列的网格 A 和 B。

对于所有满足 $1 \le i \le H$、$1 \le j \le W$ 的整数对 $(i, j)$,用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。网格 A 中格子 $(i, j)$ 上的整数为 $A_{i, j}$,网格 B 中格子 $(i, j)$ 上的整数为 $B_{i, j}$。

你可以对网格 A 进行任意次(可能为 0 次)如下操作。每次操作执行以下两种之一:

选择满足 $1 \le i \le H-1$ 的整数 $i$,交换网格 A 中第 $i$ 行和第 $(i+1)$ 行。

选择满足 $1 \le i \le W-1$ 的整数 $i$,交换网格 A 中第 $i$ 列和第 $(i+1)$ 列。

判断通过重复上述操作能否使网格 A 与网格 B 完全一致。如果可以,输出所需的最少操作次数。

这里,网格 A 与网格 B 完全一致,当且仅当对于所有满足 $1 \le i \le H$、$1 \le j \le 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 完全一致所需的最少操作次数。

样例

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

3

对初始网格 A 交换第四列和第五列,得到如下网格:

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

然后,交换第二行和第三行,得到如下网格:

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

最后,交换第二列和第三列,得到与网格 B 一致的如下网格:

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

可以通过上述三次操作使网格 A 与网格 B 完全一致,且无法用更少的操作完成,因此输出 $3$。

2 2
1 1
1 1
1 1
1 1000000000

-1

无论如何进行操作都无法使网格 A 与网格 B 一致,因此输出 -1。

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

0

初始时网格 A 就已经与网格 B 完全一致。

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

20

数据范围

• 所有输入值均为整数
• $2 \le H, W \le 5$
• $1 \le A_{i, j}, B_{i, j} \le 10^9$