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

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）坐标对

我对这个问题的看法-我将矩阵转换为字典，并使用键作为位置（x，y），其值等于0或1（当然，这是[[not最快的方法-使用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