如果每个偶数长度的方子矩阵都有奇数个 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$$$ 整除,则子矩阵进一步称为偶数长度平方。