最小面积矩阵覆盖
考虑一个 n×n 二进制矩阵，我想找到覆盖所有矩形（1）的两个矩形的最小面积。也就是说，矩形的面积之和必须最小。 矩形可以重叠。
示例：
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
最小面积为：3 * 9 + 9 * 3 = 54
我很想知道是否有比 O(n^4) 更好的解决方案。
Considering an n-by-n binary matrix, I would like to find the minimal area of two rectangles that would cover all the ones (1s). That is, the sum of the areas of the rectangles must be minimal.
The rectangles can overlap.
Example:
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
The minimal area is: 3 * 9 + 9 * 3 = 54
I'm interested to know if there is a solution better than O(n^4).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以首先通过查找矩阵中最上面、最下面、最右边和最左边的 1 来解决一个矩形的问题。然后您就知道，当且仅当您可以剪掉全 0 的对称块时，您可以通过使用第二个矩形来改进结果。
You can first solve the problem for one rectangle by finding the upmost, downmost, rightmost, and leftmost 1s in the matrix. Then you know that you can improve your result by using a second rectangle if and only if you can cut out symmetrical chunks of all 0s.