最小矩形表面 - 算法

Question

有人能指出我朝着以下問題正確的做法：我有充滿0和1，我需要找到兩個矩形值方陣（N * N）矩陣，因此它們檢查以下條件：

1. 矩陣中的每個1的元素必須包含在至少一個矩形中;

2. 兩個矩形的表面的總和必須爲最小（它是允許的，該矩形的一個有表面0）。

更具體的是什麼的矩形是：一矩形由兩個間隔[A1，B1]，[A2，B2]中定義，並且包含了所有的矩陣單元（I，J），從而A1 ≤i≤b1，a2≤j≤b2。要更清楚地表達什麼意思：（b1-a1 + 1）·（b2-a2 + 1）。

你能幫我解決一些想法嗎？非常感謝。

EDIT1：兩個矩形可能重疊。

EDIT2：一矩形的被允許在表面0

Answer 1

我的原始的方法。在最佳解決方案需要重疊矩形的情況下（例如，在0s的背景上1s的「+」），這不起作用。

1. 找到包含所有1的最小邊界矩形。
2. 你的第一個矩形從延伸左上角這個邊框和你的第二個外接矩形從該邊界矩形的 右下延伸。
3. 對於邊界矩形的頂部和底部之間的每一行R，創建從頂部至R和 從底部至R延伸的候選矩形，邊界矩形的兩個寬度。
4. 減少這兩個候選項，使它們成爲它們中1的最小邊界矩形。這些矩形對所有滿足 點1從步驟2保持在所有R.
5. 重複最小的一個，以覆蓋在整個邊界矩形每對角部，並保持最佳的解決方案的整體。

在一個有效的解決方案的幾個中途終止的嘗試之後，每一個在某些情況下失敗了，我認爲這會找到最好的解決方案的唯一方法如下：

你只需要考慮1s的邊界矩形。兩個邊界矩形不會位於該區域之外。假設邊界矩形從行（R1，C1）到（R2，C2）。

For S1 in R1 to R2 
     For S2 in S1 to R2 
      For D1 in C1 to C2 
       For D2 in D1 to C2 
        Reduce the rectangle (S1, C1)-(S2, C2) to be the minimum bounding rectangle of the 1s it contains 
        Reduce the rectangle (R1, D1)-(R2, D2) to be the minimum bounding rectangle of the 1s it contains that aren't already in the other rectangle. This is a candidate solution. 

        Reduce the rectangle (R1, D1)-(R2, D2) to be the minimum bounding rectangle of the 1s it contains. 
        Reduce the rectangle (S1, C1)-(S2, C2) to be the minimum bounding rectangle of the 1s it contains that aren't already in the other rectangle. This is another candidate solution. 

選擇您找到的最佳候選解決方案。

---

注：

• 最好的解決方案將不具有重疊的矩形，因爲這樣的解決方案總是可以通過減小矩形的一個，使之不再交疊得到改善。因此，我們只需要在步驟3中選擇一個R（而不是每個矩形的獨立最大行）。
• 無論你是按行（R）還是按列（C）拆分都沒有關係，但是不需要兩者兼而有之。爲了提高速度，你可以在邊界矩形短而胖的時候選擇行，在高和薄的時候選擇列。
• 如果您發現一個候選解決方案，其中任何一個矩形都不包含任何零，那麼它必須是最好的解決方案，您可以停止。