c++ - 选择矩形以最大化面积

Question

我有一个任意大小的二维二进制矩阵。我想在这个矩阵中找到一组矩形，显示最大面积。限制条件是:

• 矩形只能覆盖矩阵中的“0”字段，不能覆盖“1”字段。
• 每个矩形与下一个矩形之间必须有给定的距离。

所以让我通过这个矩阵进一步说明这一点:

1 0 0 1
0 0 0 0
0 0 1 0
0 0 0 0
0 1 0 0

设两个矩形之间的最小距离为 1。因此，最佳解决方案是选择角为 (1,0)-(3,1) 和 (1,3)-(4,3) 的矩形。这些矩形是最小的。彼此相距 1 个字段，并且它们不位于“1”字段上。此外，该解决方案获得了最大面积(6+4=10)。

如果最小距离为 2，则最佳距离为 (1,0)-(4,0) 和 (1,3)-(4,3)，面积为 4+4=8。

到目前为止，我已经找到了类似于这篇文章的矩形: Find largest rectangle containing only zeros in an N×N binary matrix

我将所有这些矩形保存在列表中:

list<rectangle> rectangles;

与

struct rectangle {
    int i,j; // bottom left corner of rectangle
    int width,length; // width=size in neg. i direction, length=size in pos. j direction
};

到目前为止，我只考虑过暴力破解方法，但当然，我对此并不满意。

我希望您能给我一些关于如何在我的列表中找到相应矩形的提示和技巧，我希望您能清楚我的问题。

Answer 1

以下反例表明，即使对最大面积矩形的所有组合进行强力检查也可能无法找到最佳值:

110
000
110

在上面的示例中，有 2 个最大面积矩形，每个面积为 3，一个垂直，一个水平。您不能同时选择这两个矩形，因此，如果您只能选择这些矩形的子集，那么您最好选择一个，总面积为 3。但是，如果您选择的是垂直面积为 3 的矩形，然后还取仅由最左边的两个 0 组成的非最大 1x2 矩形，您可以获得更好的总面积 5。(这是针对最小分隔距离 0；如果最小分隔距离为 1，如您的自己的示例，那么您可以只选择最左边的 0 作为 1x1 矩形，总面积为 4，这仍然比 3 好。)

对于分隔距离为 0 的特殊情况，有一个简单的算法:您可以简单地在矩阵中的每个 0 上放置一个 1x1 矩形。当分离距离严格大于 0 时，我还没有看到快速算法，尽管我现在不太确定问题是 NP 困难的，而不是几分钟前......