当前没有测试数据。

E - 不要孤立元素

得分：$500$ 分

问题陈述

给定一个 $H$ 行 $W$ 列的矩阵 $A$，其每个元素的值为 $0$ 或 $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$。对于每一个满足 $1 \leq j \leq W$ 的整数 $j$，将 $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$ 或 $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。

3 3
1 1 0
1 0 1
1 0 0

1

当 $i = 1$ 时，进行一次操作可得 $A = ((0,0,1),(1,0,1),(1,0,0))$，此时不存在孤立元素。

4 4
1 0 0 0
0 1 1 1
0 0 1 0
1 1 0 1

2

2 3
0 1 0
0 1 1

-1