全部爲1的最大尺寸平方子矩陣

Question

給出一個二元矩陣，我找出了所有1 s的最大尺寸平方子矩陣。

例如，請考慮下面的二元矩陣：

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

的最大子方陣的所有設置位是

1 1 1 
1 1 1 
1 1 1 

我搜索解決方案的網絡，我找到了一個關係構建輔助矩陣：

If M[i][j] is 1 then 
      S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 
     Else /*If M[i][j] is 0*/ 
      S[i][j] = 0 

1. 其中M[][]是原始矩陣，s[][]是輔助矩陣？
2. 這個關係是什麼意思？
3. 它有什麼用。

Answer 1

這是一個經典的動態規劃問題。和u都沒有提到整個算法如下：

構造輔助陣列，我們必須做到以下幾點：

1. 先複製第一行和第一列，因爲它是從M [] []到S [] []

2. 而對於剩餘的條目爲u提到執行以下操作：

   If M[i][j] is 1 then 
       S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 
   Else /*If M[i][j] is 0*/ 
       S[i][j] = 0 
   

3. 查找S [] []的最大入口，並用它來構建的最大大小方塊子矩陣

是什麼關係意味着什麼？

要找到最大平方，我們需要在不同的方向上找到1s的最小延伸，並將其加1以形成當前情況下的平方長度。

，以便爲您的案件S [] []將是：

0 1 1 0 1 
    1 1 0 1 0 
    0 1 1 1 0 
    1 1 2 2 0 
    1 2 2 3 1 
    0 0 0 0 0 

如果我們只是把這些即S[i][j-1], S[i-1][j]最小的，它需要左，頂部direction.However的照顧，我們還需要使確定透視正方形的左上角有1。 根據定義，S [i-1] [j-1]在位置i-1，j-1處包含一個最大平方，它的左上角給出了我們可以得到的上升和下降的上限。所以，我們也需要考慮這一點。

希望這會有所幫助！

Answer 2

您可以構建一個額外的遞歸函數，它以參數形式獲取一個currect行和col，然後查找任意大小的正方形。

從您的其他功能，如果額外的函數返回一個值，您必須進行2個調用： 一個來自（row，col + 1），另一個來自（row + 1，col）。

這是一個回溯用法，我們檢查所有選項。

Answer 3

你可以在線性時間內做到這一點。

索賠：我可以建立一個線性時間的數據結構，讓我可以在常量時間內檢查任意矩形是否滿了1。

證明：部分和;以S[i][j]爲上面1的總數，在(i, j)的左邊。在(a,b)和(c,d)之間的矩形中的1的個數，提供的(a,b)在(c,d)的上面和左邊，是S[c][d] + S[a][b] - S[a][d] - S[b][c]。

現在是在陣列上的簡單掃描：

size = 1; 
For i = 0 to m-size { 
    For j = 0 to n-size { 
    If S[i+size][j+size] - S[i][j+size] - S[i+size][j] + S[i][j] == size*size { 
     size++; j--; continue; 
    } 
    } 
} 

最後，size比最大的1 - 完整的正方形一個更大的。