D - Swapping Puzzle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 425 点

問題文

H 行 W 列の 2 つのグリッド 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} がそれぞれ書かれています。

あなたは「下記の 2 つのうちのどちらか 1 つを行う」という操作を好きな回数（ 0 回でもよい）だけ繰り返します。

  • 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) に書かれた整数が等しいこととします。

制約

  • 入力される値は全て整数
  • 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 の 4 列目と 5 列目を入れ替えると、グリッド A は下記の通りになります。

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

続けて、グリッド A の 2 行目と 3 行目を入れ替えると、グリッド A は下記の通りになります。

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

最後に、グリッド A の 2 列目と 3 列目を入れ替えると、グリッド A は下記の通りになり、グリッド B に一致します。

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

上に述べた 3 回の操作でグリッド A をグリッド B に一致させることができ、 これより少ない回数の操作でグリッド 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

Score : 425 points

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