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 翻译