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

输入输出样例 #1

输入 #1

3 3
9 4 3
2 1 8
7 6 5

输出 #1

2

输入输出样例 #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

输入输出样例 #3

输入 #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

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

输出 #4

0

说明/提示

限制条件

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