/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
H 行 W 列のマス目があり、最初、1 以上 (H\times W) 以下の整数がちょうど 1 つずつ書き込まれています。
具体的には、1\leq i\leq H, 1\leq j\leq W について、上から i 行目かつ左から j 列目のマスには S_{i,j} が書き込まれています。
以下、上から i 行目かつ左から j 列目のマスをマス (i,j) と呼びます。
次の操作を 高々 20 回 （0 回でも良い）繰り返すことで、
任意の整数の組 (i,j) (1\leq i\leq H, 1\leq j\leq W) について、
マス (i,j) に ((i-1)\times W+j) が書き込まれている状態にできるか判定し、
できる場合は必要な操作回数の最小値を出力してください。
20 回以下でできない場合（何回操作を繰り返してもできない場合を含む）は -1 を出力してください。
操作：マス目から (H-1) \times (W-1) の長方形を選んで 180 度回転させる。
より厳密には、整数 x,y (0 \leq x, y \leq 1) を選び、
1 \leq i \leq H-1, 1 \leq j \leq W-1 をみたすすべての整数の組 (i,j) について同時に、
マス (i+x,j+y) に書かれた整数をマス (H-i+x,W-j+y) に書かれた数に書き換える。
マス目に書き込まれている整数が条件をみたしていれば良く、書き込まれている向き等は考える必要がないことに注意してください。
制約
- 3\leq H,W\leq 8
- 1\leq S_{i,j}\leq H\times W
- (i,j)\neq (i',j') ならば S_{i,j}\neq S_{i',j'}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}
出力
問題文の条件をみたすために必要な操作回数の最小値を出力せよ。
ただし、20 回以下の操作で条件をみたすようにできないときは -1 を出力せよ。
入力例 1
3 3 9 4 3 2 1 8 7 6 5
出力例 1
2
次の順で操作を行うことで 2 回の操作で問題文の条件をみたすようにすることができます。
- 左上の長方形を選び、操作を行う。すなわち x=0, y=0 を選んで操作を行う。
- 右下の長方形を選び、操作を行う。すなわち x=1, y=1 を選んで操作を行う。
一方で 1 回以下の操作でみたすようにすることは不可能であるため、2 を出力します。
入力例 2
4 6 15 18 1 14 3 4 23 24 19 8 9 12 13 2 17 6 5 16 21 22 7 20 11 10
出力例 2
-1
20 回以下の操作で条件をみたすようにすることができないため、-1 を出力します。
入力例 3
4 6 1 4 13 16 15 18 21 20 9 12 23 10 17 14 5 6 3 2 11 22 7 24 19 8
出力例 3
20
入力例 4
4 3 1 2 3 4 5 6 7 8 9 10 11 12
出力例 4
0
Score: 550 points
Problem Statement
There is a grid with H rows and W columns. Initially, each integer from 1 to (H \times W) is written exactly once in the grid.
Specifically, for 1 \leq i \leq H and 1 \leq j \leq W, the cell at the i-th row from the top and the j-th column from the left contains S_{i,j}.
Below, let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.
Determine if it is possible to reach a state where, for all pairs of integers (i,j) (1 \leq i \leq H, 1 \leq j \leq W),
the cell (i,j) contains the integer ((i-1) \times W + j) by repeating the following operation at most 20 times (possibly zero).
If it is possible, print the minimum number of operations required.
If it is impossible in 20 or fewer operations (including the case where it is impossible no matter how many times the operation is repeated), print -1.
Operation: Choose a rectangle of size (H-1) \times (W-1) from the grid and rotate it 180 degrees.
More precisely, choose integers x and y (0 \leq x, y \leq 1),
and for all pairs of integers (i,j) satisfying 1 \leq i \leq H-1 and 1 \leq j \leq W-1,
simultaneously replace the integer written in cell (i+x,j+y) with the number written in cell (H-i+x,W-j+y).
Note that it is only necessary for the integers written in the cells to satisfy the condition; the orientation in which they are written does not matter.
Constraints
- 3 \leq H,W \leq 8
- 1 \leq S_{i,j} \leq H \times W
- If (i,j) \neq (i',j'), then S_{i,j} \neq S_{i',j'}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}
Output
Print the minimum number of operations required to meet the conditions of the problem statement.
If it is impossible to satisfy the conditions with 20 or fewer operations, output -1.
Sample Input 1
3 3 9 4 3 2 1 8 7 6 5
Sample Output 1
2
Operating in the following order will satisfy the conditions of the problem statement in 2 operations.
- Operate by choosing the rectangle in the top-left corner. That is, by choosing x=0 and y=0.
- Operate by choosing the rectangle in the bottom-right corner. That is, by choosing x=1 and y=1.
On the other hand, it is impossible to satisfy the conditions with one or fewer operations, so print 2.
Sample Input 2
4 6 15 18 1 14 3 4 23 24 19 8 9 12 13 2 17 6 5 16 21 22 7 20 11 10
Sample Output 2
-1
It is impossible to satisfy the conditions with 20 or fewer operations, so print -1.
Sample Input 3
4 6 1 4 13 16 15 18 21 20 9 12 23 10 17 14 5 6 3 2 11 22 7 24 19 8
Sample Output 3
20
Sample Input 4
4 3 1 2 3 4 5 6 7 8 9 10 11 12
Sample Output 4
0