← 返回题目列表

AtCoder · abc336_f

I. 旋转拼图

中文机器翻译题面 查看原题

分数: 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