我有一个二进制矩阵，我正在尝试找出可以由矩阵中的相邻元素组成的所有最大矩形。我所说的最大矩形是指所有唯一的矩形，不是任何其他矩形的子集。例如，下面的矩阵包含六个这样的矩形。
这与布景覆盖问题有关，不过这里我感兴趣的是矩形的最大数量，而不是最小数量。我尝试过的一种方法是找到所有矩形，不管大小如何，然后比较矩形，如果它们是另一个矩形的子集，则将其删除。这不是最佳方法。看起来这个场景封面问题应该不会太难。
我查看了一下，没有发现与此问题类似的问题。有 this论文，其中有一些不错的想法，但仍然离谱。这个特定问题是否有另一个名称？是否有任何现有算法可以在集合覆盖问题中找到所有可能的矩形？
最佳答案
经过更多的工作，我意识到这与布景问题并没有真正的关系。它实际上是“在二进制矩阵问题中找到不包含在任何其他矩形中的唯一矩形”。
我想出了一些很好用的东西，但我不知道它的复杂性。
基本上，线在水平和垂直方向上扫过矩阵。在每种情况下，寻找可以与下一行形成矩形的连续 1 组。这会产生许多矩形，其中一些是其他矩形的副本或子矩形。这些矩形被简化为一个唯一的集合，其中没有一个矩形是另一个矩形的子矩形。然后你就有了所有的矩形。
这是与原始帖子中的图像相关的图表:
关于algorithm - 最大矩形集覆盖，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31150398/