← 返回题目列表

Codeforces · 1391/D

D. 505问题

中文机器翻译题面 查看原题

如果每个偶数长度的方子矩阵都有奇数个 1,则称二进制矩阵为良好矩阵。

给定一个由 $$$n$$$ 行和 $$$m$$$ 列组成的二进制矩阵 $$$a$$$,确定需要更改以使其良好的最小单元格数,或者报告根本无法使其良好。

上述所有术语都有其通常含义 - 请参阅注释部分了解其正式定义。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq m \leq 10^6$$$ 和 $$$n\cdot m \leq 10^6$$$) — 分别是 $$$a$$$ 中的行数和列数。

以下 $$$n$$$ 行每行包含 $$$m$$$ 个字符,每个字符都是 0 和 1 之一。如果第 $$$i$$$ 行上的第 $$$j$$$ 个字符为 1,则 $$$a_{i,j} = 1$$$。同样,如果第 $$$i$$$ 行上的第 $$$j$$$ 个字符为 0,则 $$$a_{i,j} = 0$$$。

输出

输出使 $$$a$$$ 变得良好所需更改的最小单元格数,或者如果根本不可能,则输出 $$$-1$$$。

示例

输入 #1

3 3
101
001
110

输出 #1

2

输入 #2

7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011

输出 #2

-1

注意

在第一种情况下,将 $$$a_{1,1}$$$ 更改为 $$$0$$$ 并将 $$$a_{2,2}$$$ 更改为 $$$1$$$ 就足够了。

可以验证一下,没有办法让第二种情况下的矩阵变好。

一些定义—

- 二元矩阵是其中每个元素都是 $$$1$$$ 或 $$$0$$$ 的矩阵。
- 子矩阵由 $$$4$$$ 参数描述 - $$$r_1$$$、$$$r_2$$$、$$$c_1$$$ 和 $$$c_2$$$;这里,$$$1 \leq r_1 \leq r_2 \leq n$$$ 和 $$$1 \leq c_1 \leq c_2 \leq m$$$。
- 该子矩阵包含满足 $$$r_1 \leq i \leq r_2$$$ 和 $$$c_1 \leq j \leq c_2$$$ 的所有元素 $$$a_{i,j}$$$。
- 如果 $$$r_2-r_1 = c_2-c_1$$$ 且 $$$r_2-r_1+1$$$ 可被 $$$2$$$ 整除,则子矩阵进一步称为偶数长度平方。