/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
各要素の値が 0 または 1 である H 行 W 列の行列 A が与えられます。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす整数の組 (i,j) について、A の i 行目 j 列目の要素を A_{i,j} で表します。
行列 A に対し、以下の操作を 0 回以上の好きな回数行うことができます。
- 1 \leq i \leq H を満たす整数 i を選び、1 \leq j \leq W を満たす全ての整数 j に対して A_{i,j} の値を 1-A_{i,j} で置き換える。
また、A_{i,j} は行列において上下左右に同じ値が存在しない、すなわち 4 つの整数組 (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
Score : 500 points
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