Don't Isolate Elements

题目描述

你得到一个有 $H$ 行 $W$ 列的矩阵 $A$。矩阵中每个元素的值为 $0$ 或 $1$。 对于满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数对 $(i, j)$，我们用 $A_{i,j}$ 表示第 $i$ 行第 $j$ 列的元素。 你可以对矩阵 $A$ 重复（可能为零次）执行如下操作：

选择一个整数 $i$，满足 $1 \leq i \leq H$。对于每个满足 $1 \leq j \leq W$ 的整数 $j$，将 $A_{i,j}$ 的值替换为 $1-A_{i,j}$。

当且仅当不存在与其相邻且值相同的元素时，$A_{i,j}$ 被称为 孤立的；换句话说，当且仅当四个整数对 $(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$ 变成没有任何孤立元素的状态。如果可以，找出使之成为该状态所需的最小操作次数。

输入格式

输入从标准输入按以下格式给出： $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$。

3 3
1 1 0
1 0 1
1 0 0

1

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

提示

$2 \leq H,W \leq 1000$ $A_{i,j} = 0$ 或 $A_{i,j} = 1$ 输入中的所有值均为整数。对 $i = 1$ 的一次操作会使 $A = ((0,0,1),(1,0,1),(1,0,0))$，其中不再存在孤立元素。

标签: AtCoder|abc283E

来源

AtCoder|abc283E