我已經在SO上搜索了許多帖子以及其他在線資源。他們中的大多數提供了一個解決方案,用於在2D矩陣中查找矩形的最大面積,我知道。但是,我很想知道如何找到2D矩陣中矩形數爲(表示爲1s)的矩形數。如何找到0和1的二維矩陣中的矩形數量?
更新: 道歉不澄清的情況下,以一個長方形什麼分類 - 它被認爲是一個矩形,如果一定周邊內的細胞是充滿以1s。
我已經在SO上搜索了許多帖子以及其他在線資源。他們中的大多數提供了一個解決方案,用於在2D矩陣中查找矩形的最大面積,我知道。但是,我很想知道如何找到2D矩陣中矩形數爲(表示爲1s)的矩形數。如何找到0和1的二維矩陣中的矩形數量?
更新: 道歉不澄清的情況下,以一個長方形什麼分類 - 它被認爲是一個矩形,如果一定周邊內的細胞是充滿以1s。
這裏是一個非優化的版本,應該給予正確的結果:
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;
}
}
}
我承認在考慮是否爲提問者編寫代碼時總會找到平衡點。通常我們說我們不這樣做,主要是因爲我們不想吸引「給予編碼」這類問題。我認爲這是我們可以安全避免的情況之一,並且可以僅給出解釋性答案。我比這個更喜歡僞代碼。 –
在我看來,沒有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個。如果情況並非如此,那麼你可以儘早停止。
@sashcha,謝謝你的回答。請檢查我更新的問題。我已經澄清了什麼歸類爲矩形的細節。 –
對於rectabgle來算,做的正好角落需爲1,或雙方,還是矩形必須充滿1s? –
@ OleV.V。,我更新了我的問題。 –