← 返回题目列表

AtCoder · abc332_d

G. 交换拼图

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

给你两个网格,A 和 B,每个网格都有 H 行和 W 列。

对于每对整数 (i, j) 满意 1 \leq i \leq H 和 1 \leq j \leq W,让 (i, j) 表示单元格 i第行和 j第列。在网格 A 中,单元格 (i, j) 包含整数 A_{i, j}。在网格 B 中,单元格 (i, j) 包含整数 B_{i, j}.

您将重复以下操作任意次数,可能为零。在每个操作中,您执行以下操作之一:

  • 选择一个整数 i 满意 1 \leq i \leq H-1 并交换 i-th 和 (i+1)网格 A 中的第行。
  • 选择一个整数 i 满意 1 \leq i \leq W-1 并交换 i-th 和 (i+1)网格 A 中的第列。

重复上述操作,判断是否可以使网格A与网格B相同。如果可能,请打印执行此操作所需的最少操作数。

这里,网格 A 与网格 B 相同当且仅当,对于所有整数对 (i, j) 满意 1 \leq i \leq H 和 1 \leq j \leq W,写入单元格的整数 网格A的 (i, j) 等于单元格中写入的整数 网格 B 的 (i, j) 。

约束

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

输入

输入由标准输入按以下格式给出:

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

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

交换初始网格 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 2
1 1
1 1
1 1
1 1000000000

示例输出 2

-1

无法执行使网格 A 与网格 B 匹配的操作,因此打印 -1.


示例输入 3

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

示例输出 3

0

网格 A 一开始就已经与网格 B 相同。


示例输入 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