如何找到0和1的二維矩陣中的矩形數量？

我已經在SO上搜索了許多帖子以及其他在線資源。他們中的大多數提供了一個解決方案，用於在2D矩陣中查找矩形的最大面積，我知道。但是，我很想知道如何找到2D矩陣中矩形數爲（表示爲1s）的矩形數。如何找到0和1的二維矩陣中的矩形數量？

更新： 道歉不澄清的情況下，以一個長方形什麼分類 - 它被認爲是一個矩形，如果一定周邊內的細胞是充滿以1s。

2017-04-09 Poojith Jain

對於rectabgle來算，做的正好角落需爲1，或雙方，還是矩形必須充滿1s？ –

@ OleV.V。，我更新了我的問題。 –

這裏是一個非優化的版本，應該給予正確的結果：

int sum = 0; 
for (int row = 0; row < n; row++) { 
    for (int col = 0; col < m; col++) { 
     // count all rectangles with top left corner at (row,col) 
     int upperLimit = m; // this number sets the max width that rectangles with greater 
          // height can have (depends on the 1s in the rows above) 
     for (int r = row; r < n && matrix[r][col] == 1; r++) { 
      int c = col; 
      for (; c < upperLimit && matrix[r][c] == 1; c++) 
       sum++; 
      upperLimit = c; 
     } 
    } 
}

來源

2017-04-09 02:44:26 maraca

我承認在考慮是否爲提問者編寫代碼時總會找到平衡點。通常我們說我們不這樣做，主要是因爲我們不想吸引「給予編碼」這類問題。我認爲這是我們可以安全避免的情況之一，並且可以僅給出解釋性答案。我比這個更喜歡僞代碼。 –

在我看來，沒有10是正確的答案，我不知道你是如何得到8的。如果我們從左到右，從上到下，它是4 + 1 + 2 + 2 + 1 = 10。的僞代碼非常模糊，並且比它的複雜得多。 @ OleV.V。 – maraca

感謝您解釋我的計數錯誤。我犯了一個錯誤的一個原因是你的代碼有點棘手，應該得到比你給出的更好的解釋。 –

一些僞代碼：

for x_0 in rows: 
    for x_1 > x_0 in rows:  # symmetry-reduction: x_0 always "top" 
     for y_0 in columns: 
      for y_1 > y_0 in columns: # symmetry reduction: y_0 always "left" 
       if mat[x_0, y_0] == mat[x_0, y_1] == mat[x_1, y_0] == mat[x_1, y_1] == 1: 
        found rectangle!

請記住：這是僞代碼（部分基於Python風格）和布爾評價不一樣，在大多數語言工作！

對稱減少不僅可以提高性能，而且在計數時也很重要。在視覺上有相同的矩形，其中x_0和x_1只是承擔不同的角色（左和右點）。你必須決定如何計算這一點。

編輯：在Ole V.V.的評論上面，我意識到確實存在非常不同的解釋。這些大部分可以用上面的僞代碼來實現，但是在內部級別上有不同的檢查。但那可能是你的工作（並且在某些情況下可能有更多的調整方法）！

在這裏，我假設，一個矩形只是由1在4個角落定義！

編輯：新矩形的定義之後，內部檢查的變化：

if all(mat[x_0:x_1, y_0:y_1]) # python/numpy inspired pseudo-code!

所以基本上你可以檢查由4邊界點所定義的所有值。這很簡單，可以解決您的問題。

但是，當然你可以更有效率。添加一些二進制標誌可能是明智的，它指示當前矩形（它們正在增長）是否仍然只填滿1。其實你可能需要2個二進制標誌，每個維度1個。如果情況並非如此，那麼你可以儘早停止。

來源

2017-04-09 00:37:09 sascha

@sashcha，謝謝你的回答。請檢查我更新的問題。我已經澄清了什麼歸類爲矩形的細節。 –

如何找到0和1的二維矩陣中的矩形數量？

回答

相關問題