Как проверить суммы всех возможных прямоугольников массива

Question

Предположим, что у нас есть двумерный массив A (n X n). Все элементы матрицы А являются О или 1. Мы также имеем заданное число 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.

Другими словами, нам нужно проверить все возможные прямоугольники в A, чтобы увидеть, равна ли сумма их элементов 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).

Прежде всего обратите внимание на то, что a summed area table позволяет вычислить сумму любого прямоугольника в O (1), заданном временем O (n^2) предварительной обработки.

В этой задаче нам нужно только суммировать столбцы, но общая техника стоит знать.

Затем для каждой комбинации начальных строк и конечных строк вы можете выполнять линейное сканирование по матрице для подсчета решений либо с помощью двух указателей, либо просто путем хранения предыдущих сумм.

Пример 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