消除孤立元素

题目描述

给定一个 $H$ 行 $W$ 列的矩阵 $A$,每个元素的值是 $0$ 或 $1$。 对于满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数对 $(i, j)$,用 $A_{i,j}$ 表示第 $i$ 行第 $j$ 列的元素。

可以对矩阵 $A$ 进行任意次(可能为 0 次)以下操作:

• 选择一个整数 $i$,满足 $1 \leq i \leq H$。对于所有整数 $j$,满足 $1 \leq j \leq W$,将 $A_{i,j}$ 的值替换为 $1-A_{i,j}$。

当且仅当 $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_{i,j}$ 是孤立的。

判断能否通过重复执行操作,使矩阵 $A$ 达到没有任何元素孤立的状态。如果可能,求出所需的最小操作次数。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $2 \le H,W \le 1000$
• $A_{i,j} = 0$ 或 $A_{i,j} = 1$
• 输入中的所有值均为整数。