← 返回题目列表

AtCoder · abc283_e

H. 不要隔离元素

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

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