基于值的最大元素组数组搜索算法

Question

我需要一个搜索算法，可以在0和1的矩阵中找到最大的矩形，主要是1；具体来说，我需要它返回这些矩形的左上角和右下角的（x，y）坐标对。你知道吗

例如，考虑以下矩阵：

[1,1,0,0,0,
 1,0,0,0,0,
 0,0,0,0,0,
 0,0,0,1,1,
 0,0,0,1,1]

如果我将阈值设置为75%（矩形的平均值为0.75），那么在矩阵的左上角和右下角会找到两个矩形（特别是正方形）。每个点的元组输出分别是左上（x，y），右下（x，y）。你知道吗

{rectangle_1: ((0,0),(1,1)),
rectangle_2: ((3,3),(4,4))} 

是否有任何数组/矩阵搜索算法可以作为此任务的起点？你知道吗

如果有什么重要的，我将使用python。因此，如果这样一个算法有python实现，那将是非常感激的。你知道吗

Answer 1

我对这个问题的看法-我将矩阵转换为字典，其中键作为位置（x，y），值等于0或1（当然，这是而不是最快的方法-使用NumPy肯定更好）：

from itertools import count

lst = [
 1,1,0,0,0,
 1,0,0,0,0,
 0,0,0,0,0,
 0,0,0,1,1,
 0,0,0,1,1]

def get_values(d, i1, j1, i2, j2):
    c = 0
    s = 0
    for i in range(i1, i2+1):
        for j in range(j1, j2+1):
            s += d[(i, j)]
            c += 1
    return s / c

def find_squares(lst, m, n, t):
    lst = iter(lst)
    d = {(j, i): next(lst) for i in range(m) for j in range(n)}

    seen_squares = []

    for i1 in range(m):
        for j1 in range(n):
            ii2 = count(i1+1)
            ij2 = count(j1+1)

            i2 = next(ii2)
            j2 = next(ij2)
            current_square = None
            while i2 < m and j2 < n:
                if get_values(d, i1, j1, i2, j2) >= t:
                    current_square = i1, j1, i2, j2
                else:
                    break

                i2 = next(ii2)
                j2 = next(ij2)

            if current_square:
                for x1, y1, x2, y2 in seen_squares:
                    if i1 >= x1 and i2 - 1  <= x2 and j1 >= y1 and j2 - 1 <= y2:
                        break
                else:
                    seen_squares.append(current_square)
                    yield current_square

for i1, j1, i2, j2 in find_squares(lst, 5, 5, 0.75):
    print(i1, j1, i2, j2)

印刷品：

0 0 1 1
3 3 4 4

对于矩阵：

lst = [
 1,1,0,0,0,
 1,0,0,0,0,
 0,0,0,1,1,
 0,0,0,1,1,
 0,0,0,1,1]

输出为：

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