atcoder#ABC283E. [ABC283E] Don't Isolate Elements
[ABC283E] Don't Isolate Elements
Score : points
Problem Statement
You are given a matrix with rows and columns. The value of each of its elements is or . For an integer pair such that and , we denote by the element at the -th row and -th column.
You can perform the following operation on the matrix any number of times (possibly zero):
- Choose an integer such that . For every integer such that , replace the value of with .
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 satisfies , and .
Determine if you can make the matrix 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
- or
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
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 makes , 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