旋转拼图

题目描述

有一个 $H$ 行 $W$ 列的网格。初始时，$1$ 到 $H \times W$ 的每个整数恰好各出现一次在网格中。

具体来说，对于 $1 \le i \le H$ 且 $1 \le j \le W$，从上方数第 $i$ 行、从左数第 $j$ 列的格子中写着 $S_{i,j}$。

下面，用 $(i,j)$ 表示从上方数第 $i$ 行、从左数第 $j$ 列的格子。

请判断能否通过重复进行以下操作至多 $20$ 次（可以是零次），达到对所有整数对 $(i,j)$（$1 \le i \le H$，$1 \le j \le W$）都满足格子 $(i,j)$ 中写着整数 $((i-1) \times W + j)$ 的状态。

如果可以，请输出所需的最少操作次数。

如果在 $20$ 次以内无法达到（包括无论重复多少次都无法达到的情况），请输出 $-1$。

操作：选择网格中一个大小为 $(H-1) \times (W-1)$ 的矩形，将其旋转 $180$ 度。

更精确地说，选择整数 $x$ 和 $y$（$0 \le x, y \le 1$），对所有满足 $1 \le i \le H-1$、$1 \le j \le W-1$ 的整数对 $(i,j)$，同时把格子 $(i+x,j+y)$ 中写的整数替换为格子 $(H-i+x,W-j+y)$ 中写的数。

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

输入格式

输入按以下格式从标准输入给出:

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

样例

3 3
9 4 3
2 1 8
7 6 5

2

按以下顺序操作，可以在 $2$ 次操作内满足题目条件。

选择左上角的矩形进行操作。即选择 $x=0$、$y=0$。

选择右下角的矩形进行操作。即选择 $x=1$、$y=1$。

另一方面，无法在 $1$ 次或更少的操作内满足条件，所以输出 $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

-1

无法在 $20$ 次或更少的操作内满足条件，所以输出 $-1$。

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

20

4 3
1 2 3
4 5 6
7 8 9
10 11 12

0

数据范围

• $3 \le H, W \le 8$
• $1 \le S_{i,j} \le H \times W$
• 如果 $(i,j) \neq (i',j')$，则 $S_{i,j} \neq S_{i',j'}$
• 所有输入均为整数。