atcoder#ABC283E. [ABC283E] Don't Isolate Elements

[ABC283E] Don't Isolate Elements

Score : 500500 points

Problem Statement

You are given a matrix AA with HH rows and WW columns. The value of each of its elements is 00 or 11. For an integer pair (i,j)(i, j) such that 1iH1 \leq i \leq H and 1jW1 \leq j \leq W, we denote by Ai,jA_{i,j} the element at the ii-th row and jj-th column.

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

  • Choose an integer ii such that 1iH1 \leq i \leq H. For every integer jj such that 1jW1 \leq j \leq W, replace the value of Ai,jA_{i,j} with 1Ai,j1-A_{i,j}.

Ai,jA_{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)=(i1,j),(i+1,j),(i,j1),(i,j+1)(x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1) satisfies 1xH,1yW1 \leq x \leq H, 1 \leq y \leq W, and Ai,j=Ax,yA_{i,j} = A_{x,y}.

Determine if you can make the matrix AA 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

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

Input

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

HH WW

A1,1A_{1,1} A1,2A_{1,2} \ldots A1,WA_{1,W}

A2,1A_{2,1} A2,2A_{2,2} \ldots A2,WA_{2,W}

\vdots

AH,1A_{H,1} AH,2A_{H,2} \ldots AH,WA_{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.

3 3
1 1 0
1 0 1
1 0 0
1

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

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