分数: 550 点
问题陈述
有一个网格 H 行和 W 列。最初,每个整数来自 1 to (H \times W) 在网格中只写入一次。
具体来说,对于 1 \leq i \leq H 和 1 \leq j \leq W,位于 i从顶部开始的第行和 j左起第 列包含 S_{i,j}.
下面,让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
确定是否有可能达到这样的状态:对于所有整数对 (i,j) (1 \leq i \leq H, 1 \leq j \leq W),
细胞 (i,j) 包含整数 ((i-1) \times W + j) 通过重复以下操作 最多 20 次 (可能为零)。
如果可能,请打印所需的最少操作数。
如果不可能 20 或更少的操作(包括无论重复多少次操作都不可能的情况),打印 -1.
操作:选择一个大小为矩形的矩形 (H-1) \times (W-1) 从网格中旋转它 180 度。
更准确地说,选择整数 x 和 y (0 \leq x, y \leq 1),
以及所有整数对 (i,j) 满意 1 \leq i \leq H-1 和 1 \leq j \leq W-1,
同时替换单元格中写入的整数 (i+x,j+y) 与单元格中写入的数字 (H-i+x,W-j+y).
注意,只需单元格中写入的整数满足条件即可;它们的书写方向并不重要。
约束
- 3 \leq H,W \leq 8
- 1 \leq S_{i,j} \leq H \times W
- If (i,j) \neq (i',j'),那么 S_{i,j} \neq S_{i',j'}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
3 3 9 4 3 2 1 8 7 6 5
示例输出 1
2
按以下顺序操作将满足问题陈述中的条件 2 操作。
- 通过选择左上角的矩形进行操作。也就是说,通过选择 x=0 和 y=0.
- 通过选择右下角的矩形进行操作。也就是说,通过选择 x=1 和 y=1.
另一方面,不可能用一次或更少的操作来满足条件,因此打印 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
不可能满足条件 20 或更少的操作,因此打印 -1.
示例输入 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 3 1 2 3 4 5 6 7 8 9 10 11 12
示例输出 4
0