最小區域矩陣覆蓋

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的對稱塊，就可以通過使用第二個矩形來改善結果。