java - 使用最少 "XOR"操作重新创建二进制矩阵

Question

这是不久前的高中学位编码竞赛问题。基本想法是仅通过矩形异或运算(或者他们这么调用它)来重新创建一幅黑白画。

问题

让我们假设我们有这幅我们正在尝试重新创建的画(表示为二进制矩阵，0 表示黑色，1 表示白色):

1 0 0
1 1 1
1 0 1

重建这幅画的一种方法是以下操作:

(0, 0) (2, 2)
(1, 0) (2, 0)
(1, 2) (1, 2)

操作的形式为(xStart, yStart) (xEnd, yEnd)

因此，如果我们从全黑 Canvas 开始，上述操作将执行以下操作:

beginning:

    0 0 0
    0 0 0
    0 0 0

after (0, 0) (2, 2) :

    1 1 1
    1 1 1
    1 1 1

after (1, 0) (2, 0) :

    1 0 0
    1 1 1
    1 1 1

after (1, 2) (1, 2) :

    1 0 0
    1 1 1
    1 0 1

---

关于作业的技术:

• 获胜者的操作最少。
• 一个操作的形式应该是(xStart, yStart) (xEnd, yEnd)。
• 没有时间或空间限制。
• 在作业中，我们尝试重新创作的画作大小为 200x200，并使用 2000 次随机异或运算生成。

---

我的想法

我想出了几个方法来做到这一点。我将在此处按从坏到好的顺序列出它们。

异或所有像素:

我们可以通过简单地将 1 写入空白 Canvas 来重新创建这幅画，其中 1 驻留在我们试图重新创建的画中。这个解决方案是所有解决方案中最简单和最明显的。所需的操作次数基本上就是画中白色像素的数量。

异或所有水平相邻的白色:

这是对第一个解决方案的重大改进，但仍然非常简单明了。在这种方法中，我们简单地异或所有水平相邻的白色。这样，例如操作

(0, 0) (0, 0)
(1, 0) (1, 0)
(2, 0) (2, 0)

将减少到 (0, 0) (2, 0)。

异或矩形:

我认为这是对之前方法的明显跟进，我们可以将其视为高度为 1 的矩形的异或运算 - 现在我们只需向矩形添加第二个维度，进一步改进我们的结果。我通过获取白色最多的矩形来确定 XORable 区域。改进还是不错的。

异或最大的区别:

这与上述方法略有不同，并且更加蛮力。在这种方法中，我找到与绘画差异最大的矩形，并对它进行异或。例如，如果我们有这幅画

1 0 1
0 1 1
0 1 0

和全黑 Canvas ，最大的区别在于矩形(0, 0) (2, 1)，它的区别是2。我通过获取所有绘画的不同颜色，在上述情况下为 4，然后从中减去相同颜色的数量，在上述情况下为 2。所以 different_colors - same_colors = difference。

在上面的绘画和空白 Canvas 中，有许多矩形产生相同的差异。另一个是 (1, 0) (2, 2)。

这种方法相对于前一种大型绘画的改进最小，但仍然是一种改进。有趣的是，这种方法有时会得出比之前的小画作更糟糕的解决方案(虽然不记得有多小了)。

---

我拥有的用于上述方法的任何代码早已丢失。你能想出令人叹为观止的解决方案吗？是否有来自外太空的神奇方法？我发现这个问题(帖子)很有趣，想看看是否有人能提出任何建议。

---

关于标签

我用 Java 和 C++ 标记了这个，不是因为这个问题特别涉及那些语言，而是因为我可以轻松理解用这些语言编写的任何代码，以及具有相似语法的语言。

Answer 1

我认为，要完成这个任务，我们需要找到仅包含零的最大尺寸子矩阵的坐标。

我可以解释该算法，但我认为以下链接有最好的解释:

Maximum size sum-matrix with all 1s in binary matrix

这里的解决方案是针对全1的，我们可以修改为全0。

然后我们只需要从最大值中找到坐标，就可以进行运算了。

如果我能想到更好的方法，我会更新。