103323: [Atcoder]ABC332 D - Swapping Puzzle

Problem Statement

You are given two grids, A and B, each with $H$ rows and $W$ columns.

For each pair of integers $(i, j)$ satisfying $1 \leq i \leq H$ and $1 \leq j \leq W$, let $(i, j)$ denote the cell in the $i$-th row and $j$-th column. In grid A, cell $(i, j)$ contains the integer $A_{i, j}$. In grid B, cell $(i, j)$ contains the integer $B_{i, j}$.

You will repeat the following operation any number of times, possibly zero. In each operation, you perform one of the following:

• Choose an integer $i$ satisfying $1 \leq i \leq H-1$ and swap the $i$-th and $(i+1)$-th rows in grid A.
• Choose an integer $i$ satisfying $1 \leq i \leq W-1$ and swap the $i$-th and $(i+1)$-th columns in grid A.

Determine whether it is possible to make grid A identical to grid B by repeating the above operation. If it is possible, print the minimum number of operations required to do so.

Here, grid A is identical to grid B if and only if, for all pairs of integers $(i, j)$ satisfying $1 \leq i \leq H$ and $1 \leq j \leq W$, the integer written in cell $(i, j)$ of grid A is equal to the integer written in cell $(i, j)$ of grid B.

Constraints

• All input values are integers.
• $2 \leq H, W \leq 5$
• $1 \leq A_{i, j}, B_{i, j} \leq 10^9$

Input

The input is given from Standard Input in the following format:

$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}$

Output

If it is impossible to make grid A identical to grid B, output -1. Otherwise, print the minimum number of operations required to make grid A identical to grid B.

Sample Input 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

Sample Output 1

3

Swapping the fourth and fifth columns of the initial grid A yields the following grid:

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

Then, swapping the second and third rows yields the following grid:

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

Finally, swapping the second and third columns yields the following grid, which is identical to grid B:

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

You can make grid A identical to grid B with the three operations above and cannot do so with fewer operations, so print $3$.

Sample Input 2

2 2
1 1
1 1
1 1
1 1000000000

Sample Output 2

-1

There is no way to perform the operation to make grid A match grid B, so print -1.

Sample Input 3

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

Sample Output 3

0

Grid A is already identical to grid B at the beginning.

Sample Input 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

Sample Output 4

20

问题描述

给你两个大小为 $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 相同所需的最小操作数。

这里，网格 A 与网格 B 相同当且仅当，对于满足 $1 \leq i \leq H$ 和 $1 \leq j \leq W$ 的所有整数对 $(i, j)$，网格 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 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 71051