103365: [Atcoder]ABC336 F - Rotation Puzzle

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

问题描述

有一个包含$H$行和$W$列的网格。最初，网格中的每个整数从1到$(H \times W)$恰好写一次。
具体来说，对于$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