AT_abc336_f.[ABC336F] Rotation Puzzle

有一个 $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)$ 中的整数交换。

注意，只要格子中写有的整数满足条件即可，不需要考虑写入的方向等其它因素。

输入按以下格式从标准输入读入。

$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\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'}$
• 输入均为整数

样例解释 1

按照如下顺序进行操作，可以在 $2$ 次操作内满足题目条件：

• 选择左上角的矩形区域进行操作，即选择 $x=0$，$y=0$。
• 选择右下角的矩形区域进行操作，即选择 $x=1$，$y=1$。
  而无法在 $1$ 次或更少操作内达成条件，因此输出 $2$。

样例解释 2

无法在 $20$ 次以内达成条件，因此输出 $-1$。

由 ChatGPT 4.1 翻译