AT_abc283_e [ABC283E] Don‘t Isolate Elements

题目描述

给定一个 $H$ 行 $W$ 列的矩阵 $A$，每个元素的值为 $0$ 或 $1$。对于满足 $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$，将第 $i$ 行的所有元素 $A_{i,j}$（$1 \leq j \leq W$）替换为 $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} \neq A_{x,y}$），则称 $A_{i,j}$ 为孤立元素。

请判断是否可以通过若干次操作，使得矩阵 $A$ 中不存在孤立元素。如果可以，输出所需操作次数的最小值；如果不可以，输出 $-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

输入 #1

3 3
1 1 0
1 0 1
1 0 0

输出 #1

1

输入输出样例 #2

输入 #2

4 4
1 0 0 0
0 1 1 1
0 0 1 0
1 1 0 1

输出 #2

2

输入输出样例 #3

输入 #3

2 3
0 1 0
0 1 1

输出 #3

-1

说明/提示

限制条件

• $2 \leq H, W \leq 1000$
• $A_{i,j} = 0$ 或 $A_{i,j} = 1$
• 输入均为整数

样例解释 1

选择 $i = 1$ 进行操作后，$A = ((0,0,1),(1,0,1),(1,0,0))$，此时不存在孤立元素。

由 ChatGPT 4.1 翻译