Score: $550$ points

问题描述

存在一个具有 $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次（可能为零次）达到一种状态：对于所有整数对 $(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)$ 写有的数字。

注意，只需满足格子中所写的整数满足条件即可；它们的书写方向无关紧要。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:26:09