E - Don't Isolate Elements

Contest Duration: 2022-12-24(Sat) 12:00 - 2022-12-24(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Don't Isolate Elements Editorial

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 を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$i = 1$ を選択し操作を行うと、 $A = ((0,0,1),(1,0,1),(1,0,0))$ となり、孤立した要素は存在しなくなります。

入力例 2Copy

Copy

出力例 2Copy

Copy

入力例 3Copy

Copy

2 3
0 1 0
0 1 1

出力例 3Copy

Copy

-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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

2 3
0 1 0
0 1 1

Sample Output 3Copy

Copy

-1