如何檢查數組中所有可能的矩形的總和

Question

讓我們假設我們有一個二維數組A（n X n）。 A的所有元素是0或1。我們也有一定的整數K.我們的任務是找到一個所有可能的「矩形」，其中包含總金額的元素個數K.

To give an example , if A = 
0 0 1 0 
1 0 0 1 
1 1 1 1 
1 0 0 1 and k=3 , 

0 0 1 0 
1 0 0 1 holds the property , 

1 1 1 holds the property , 

    1 1 1 holds the property , 

0 0 
1 0 
1 1 holds the property , 

1 1 
1 0 holds the property , 

    1 1 
    0 1 holds the property , 

1 
1 
1 holds the property 

1 
1 
1 holds the property 

所以除非我錯過了一些東西，這個例子的答案應該是8。

換句話說，我們需要簽入所有可能的矩形，看看他們的元素之和是K.有沒有辦法做到這一點爲O快（N^2 * K^2）？

Answer 1

我認爲這是比你計算差。我發現總共14個矩形和三個1（綠色方塊）。我使用的方法是將數組中的每個{row,column}位置作爲矩形的左上角，然後考慮寬度和高度的每種可能組合。

由於寬度和高度不受k（至少不直接）的約束，因此搜索時間爲O(n^4)。當然，對於任何給定的{row,column,width}，當高度大於k時，搜索結束。但是這並不能改變最壞的情況。

在右下方的三個出發點不需要被考慮，因爲這是不可能的，以構建含有k 1的從這些位置開始的矩形。但是，這並不能改變時間複雜性。

_{注：我知道，這是一個多回答評論的。但是，它不適合評論，我相信它對OP仍然有用。直到你完全理解它，你才能解決問題。}

Answer 2

你可以爲O做到這一點（N^3）。

首先請注意，summed area table允許您計算在給定O（n^2）預處理時間的情況下O（1）時間內任意矩形的總和。

在這個問題上，我們只需要總結的列，但總的技術是值得了解的。

然後對每個開始行和結束行的組合，你可以做線性掃描跨矩陣計算或者用兩個指針接近或簡單地通過存儲先前的資金解決方案。

例Python代碼（發現14個解決方案，以你的例子）：

from collections import defaultdict 
A=[[0, 0, 1, 0], 
[1, 0, 0, 1], 
[1, 1, 1, 1], 
[1, 0, 0, 1]] 
k=3 

h=len(A) 
w=len(A[0]) 

C=[ [0]*w for i in range(h+1)] 
for x in range(w): 
    for y in range(1,h+1): 
     C[y][x] = C[y-1][x] + A[y-1][x] 
# C[y][x] contains sum of all values A[y2][x] with y2<y 

count=0 
for start_row in range(h): 
    for end_row in range(start_row,h): 
     D=defaultdict(int) # Key is sum of columns from start to here, value is count 
     D[0]=1 
     t=0 # Sum of all A[y][x] for x <= col, start_row<=y<=end_row 
     for x in range(w): 
      t+=C[end_row+1][x] - C[start_row][x] 
      count += D[t-k] 
      D[t] += 1 
print count