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