algorithm - 通过翻转单元格将二进制矩阵转换为零矩阵的贪心算法

Question

我们有一个包含 1 和 0 的 M*N 矩阵，我们想使用 2*2 的正方形使所有这些单元格为零。当这个正方形被推到 4 个单元格上时，它们的内容将被翻转。我们想找出给定矩阵是否有任何答案可以将所有单元格完全转换为零。

这个有贪心的答案吗？

Answer 1

将较大的矩阵称为 M，将较小的矩阵(2x2)称为 P

在 M 上从左到右，从上到下扫描你的 P。每当 M 上 P 单元格的左上角为 1 时，应用 P。

当您到达 M 的右下角时，除了 M 的右手列和底行之外的每个单元格都保证为 0。

如果最后一列不为零，则无解。

你可以证明不是每个矩阵都能被这个过程清零。例如，如果 M 是一个 2x2 非零矩阵，则永远无法使用此过程将其清除。

1 到 3 个单元格设置为 1 的任何大小的任何矩阵 M 也不能。

我怀疑存在更普遍的无法解决的情况 - 例如可能是没有 4 位的倍数设置为 1 的矩阵不能用这种方法求解。

再考虑一下 - 我不认为你可以解决任何行或列上有奇数个 1 的矩阵。