Найти наибольший прямоугольник в матрице

Question

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

def largest_rectangle():
    rows = len(matrix)
    cols = len(matrix[0])
    maxarea = 0

    for r in range(rows):
        for c in range(cols):
            for height in range(1, rows - r + 1):
                for width in range(1, cols - c + 1):
                    valid = rectangle_area(grid, r, c, width, height)
                    if valid:
                        maxarea = max(maxarea, width * height)

    return maxarea

def rectangle_area(grid, r, c, width, height):
    for r in range(r, height + r):
        for c in range(c, width + c):
            if matrix[r][c] == 0:
                return False
    return True

Примеры прямоугольника под углом:

1 1 0 0 0
0 1 1 0 0
0 0 1 1 0
0 0 0 1 1
1 1 0 0 0

0 0 0 1 1
0 0 1 1 0
0 1 1 0 0
1 1 0 0 0
0 0 0 1 1

Прямоугольник с прямыми углами:

0 0 1 1 0
0 0 1 1 0
1 0 1 1 0
0 1 1 0 1
0 0 0 1 0

Answer 1

valid = rectangle_area(grid, row, col, width, height, 0) or rectangle_area(grid, row, col, width, height, -1) or rectangle_area(grid, row, col, width, height, 1)  

def rectangle_area(grid, r, c, width, height, delta):
    for r in range(r, height + r):
        for c1 in range(c, width + c):
            if grid[r][c1] == 0:
                return False
        c = c + delta
    return True

Добавьте в rectangle_area проверки на выход за пределы матрицы.

БЛОГ НА HUSL

Найти наибольший прямоугольник в матрице

Ответы (1 шт):