分数: 500 点
问题陈述
给你一个矩阵 A 与 H 行和 W 列。 其每个元素的值为 0 or 1。 对于整数对 (i, j) 这样 1 \leq i \leq H 和 1 \leq j \leq W,我们表示为 A_{i,j} 处的元素 i第行和 j第列。
可以对矩阵进行以下操作 A 任意次数(可能为零):
- 选择一个整数 i 这样 1 \leq i \leq H。 对于每个整数 j 这样 1 \leq j \leq W,替换值 A_{i,j} 与 1-A_{i,j}.
A_{i,j} 据说是 隔离 当且仅当不存在具有相同值的相邻元素;换句话说,当且仅当四个整数对中没有一个 (x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1) 满足 1 \leq x \leq H, 1 \leq y \leq W,和 A_{i,j} = A_{x,y}.
确定是否可以制作矩阵 A 在这样的状态下,通过重复操作没有元件被隔离。 如果可能的话,找出执行此操作所需的最少操作数。
约束
- 2 \leq H,W \leq 1000
- A_{i,j} = 0 or A_{i,j} = 1
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
输出
如果可以通过重复操作使其处于没有元素被隔离的状态,则打印所需的最少操作数;否则,打印 -1.
示例输入 1
3 3 1 1 0 1 0 1 1 0 0
示例输出 1
1
操作 i = 1 使 A = ((0,0,1),(1,0,1),(1,0,0)),不再是孤立的元素。
示例输入 2
4 4 1 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1
示例输出 2
2
示例输入 3
2 3 0 1 0 0 1 1
示例输出 3
-1