Swapping Puzzle

题目描述

给你两个网格 A 和 B，它们各有 $H$ 行 $W$ 列。 对于满足 $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 一致所需的最小操作次数。

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

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

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

2 2
1 1
1 1
1 1
1 1000000000

-1

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

0

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 \leq H, W \leq 5$ $1 \leq A_{i, j}, B_{i, j} \leq 10^9$将初始网格 A 的第四列和第五列交换，得到如下网格：

然后，交换第二行和第三行，得到如下网格：

最后，交换第二列和第三列，得到如下与网格 B 相同的网格：

你可以通过上述三个操作使网格 A 与网格 B 一致，且不能用更少的操作做到这一点，因此输出 $3$。
没有办法通过操作使网格 A 与网格 B 匹配，所以输出 $-1$。
网格 A 在一开始就已经与网格 B 一致。

标签: AtCoder|abc332D

来源

AtCoder|abc332D