这是不久前的一个高中学位编码竞赛问题。基本的想法是仅使用矩形XOR操作重新创建黑白绘画,或者这就是他们所说的。
问题所在
让我们假设我们有这幅我们试图重新创建的画(表示为二进制矩阵,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)
的形式
因此,如果我们从全黑画布开始,上述操作将执行以下操作:
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 次随机 XOR 操作生成。
我自己的想法
我想出了几种方法来做到这一点。我将按从差到好的顺序在这里列出它们。
异或所有像素:
我们可以通过简单地将 1 写到空白画布上来重新创建绘画,其中 1 位于我们试图重新创建的绘画中。这个解决方案是最简单和最明显的。所需的操作次数基本上是绘画中白色像素的数量。
XOR 所有水平相邻的白色:
与第一个解决方案相比,这是一个实质性的改进,但仍然非常简单和明显。在这种方法中,我们简单地对所有水平相邻的白色进行异或运算。这样,例如操作
(0, 0) (0, 0)
(1, 0) (1, 0)
(2, 0) (2, 0)
将减少到(0, 0) (2, 0)
.
异或矩形:
我认为这是对先前方法的明显跟进,我们可以将其视为高度为 1 的 XOR 矩形 - 现在我们只需向矩形添加第二个维度,进一步改进我们的结果。我通过获得白色最多的矩形来确定 XOR 可识别区域。改进还是不错的。
异或最大的区别:
这与上述方法略有不同,并且更加暴力。在这种方法中,我找到了与绘画差异最大的矩形,并对其进行了 XOR 运算。例如,如果我们有这幅画
1 0 1
0 1 1
0 1 0
而全黑的画布,最大的区别在于矩形(0, 0) (2, 1)
,相差2。我通过得到绘画的所有非相同颜色来计算差异,在上述情况下为 4,然后从中减去相同颜色的数量,在上述情况下为 2。所以different_colors - same_colors = difference
.
在上面的绘画和空白画布中,有许多矩形产生相同的差异。另一个是(1, 0) (2, 2)
。
这种方法与前一种大型绘画相比,改进最小,但仍然有所改进。有趣的是,这种方法有时会想出比前一个小画更糟糕的解决方案(虽然不记得有多小(。
我为上述方法编写的任何代码早已丢失。你能想出令人叹为观止的解决方案吗?有没有来自外太空的神奇方法?我觉得这个问题(帖子(很有趣,想看看是否有人能想出任何东西。
关于标签
我用Java和C++标记了这一点,不是因为这个问题特别涉及这些语言,而是因为我可以很容易地理解用这些语言编写的任何代码,以及具有类似语法的语言。
我认为,要完成此任务,我们需要找到仅包含零的最大大小子矩阵的坐标。
我可以解释该算法,但我认为以下链接有最好的解释:
二进制矩阵中所有 1 的最大大小和矩阵
这里的解决方案适用于所有 1,我们可以为所有 0 修改它。
然后我们需要做的就是从最大值中找到坐标,然后我们就可以进行操作。
如果我能想到一些更好的方法,我会更新。