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 3
9 4 3
2 1 8
7 6 5

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

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 \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'}$ 所有输入值均为整数。按以下顺序操作可以在 $2$ 次操作内满足问题陈述中的条件。

先选择左上角的矩形进行操作。也就是选择 $x=0$ 且 $y=0$。 再选择右下角的矩形进行操作。也就是选择 $x=1$ 且 $y=1$。

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

标签: AtCoder|abc336F

来源

AtCoder|abc336F