9174: ABC283 —— E - Don't Isolate Elements
[Creator : ]
Description
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.
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.
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}$
```
```
$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`.
Constraints
- $2 \leq H,W \leq 1000$
- $A_{i,j} = 0$ or $A_{i,j} = 1$
- All values in the input are integers.
- $A_{i,j} = 0$ or $A_{i,j} = 1$
- All values in the input are integers.
Sample 1 Input
3 3
1 1 0
1 0 1
1 0 0
Sample 1 Output
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 2 Input
4 4
1 0 0 0
0 1 1 1
0 0 1 0
1 1 0 1
Sample 2 Output
2
Sample 3 Input
2 3
0 1 0
0 1 1
Sample 3 Output
-1
HINT
相同题目：ABC283。