最小面积矩阵覆盖

Question

考虑到n乘n二进制矩阵,我想找到两个矩形的最小区域,它将覆盖所有的(1s).也就是说,矩形区域的总和必须是最小的.矩形可以重叠.

例:

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).

Answer 1

您可以首先通过查找矩阵中最上面、最下面、最右边和最左边的 1 来解决一个矩形的问题。然后您就知道，当且仅当您可以剪掉全 0 的对称块时，您可以通过使用第二个矩形来改善结果。