102834: [Atcoder]ABC283 E - Don't Isolate Elements

Problem Statement

You are given a matrix $A$ with $H$ rows and $W$ columns. The value of each of its elements is $0$ or $1$. For an integer pair $(i, j)$ such that $1 \leq i \leq H$ and $1 \leq j \leq W$, we denote by $A_{i,j}$ the element at the $i$-th row and $j$-th column.

You can perform the following operation on the matrix $A$ any number of times (possibly zero):

• Choose an integer $i$ such that $1 \leq i \leq H$. For every integer $j$ such that $1 \leq j \leq W$, replace the value of $A_{i,j}$ with $1-A_{i,j}$.

$A_{i,j}$ is said to be isolated if and only if there is no adjacent element with the same value; in other words, if and only if none of the four integer pairs $(x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1)$ satisfies $1 \leq x \leq H, 1 \leq y \leq W$, and $A_{i,j} = A_{x,y}$.

Determine if you can make the matrix $A$ in such a state that no element is isolated by repeating the operation. If it is possible, find the minimum number of operations required to do so.

Constraints

• $2 \leq H,W \leq 1000$
• $A_{i,j} = 0$ or $A_{i,j} = 1$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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}$ 

Output

If you can make it in such a state that no element is isolated by repeating the operation, print the minimum number of operations required to do so; otherwise, print -1.

Sample Input 1

3 3
1 1 0
1 0 1
1 0 0

Sample Output 1

1

An operation with $i = 1$ makes $A = ((0,0,1),(1,0,1),(1,0,0))$, where there is no longer an isolated element.

Sample Input 2

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

Sample Output 2

2

Sample Input 3

2 3
0 1 0
0 1 1

Sample Output 3

-1

问题描述

给你一个矩阵$A$，有$H$行和$W$列。矩阵中的每个元素的值为0或1。

对于整数对$(i, j)$，满足$1 \leq i \leq H$和$1 \leq j \leq W$，我们用$A_{i,j}$表示在第$i$行和第$j$列的元素。

你可以对矩阵$A$进行任意次数的操作（包括0次）：

• 选择一个整数$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。

样例输入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