分数: 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