1

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

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

6
  • 1
    Что такое "параллелограм в матрице" и под каким "углом"?
    – user176262
    1 ноя 2020 в 23:59
  • @Igor исправила вопрос, извините, не знаю как лучше обьяснить. С этим кодом я могу найти больший прямоугольник, который имеет прямые стороны, другие примеры показывают что прямоугольник может быть "под углом", максимум +- 1 элемент.
    – W Szum
    2 ноя 2020 в 0:06
  • 1
    Ага, начинает проясняться.
    – user176262
    2 ноя 2020 в 0:36
  • искать две "1" и дальше смотреть диагонали, но прямоугольниками я б их не назвал) 2 ноя 2020 в 1:10
  • @MikeWaters должно работать и с большим количеством единиц в ряду, пример с двумя чтобы объяснить. :)
    – W Szum
    2 ноя 2020 в 1:20

1 ответ 1

0
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 проверки на выход за пределы матрицы.

6
  • if grid[r][c] == 0: IndexError: list index out of range. Если использовать try/except, то счет получается не верным.
    – W Szum
    2 ноя 2020 в 3:05
  • @WSzum Я же написал, что нужны проверки на выход за пределы матрицы.
    – user176262
    2 ноя 2020 в 3:09
  • @WSzum Если использовать для этого try/except, то надо возвращать False из except.
    – user176262
    2 ноя 2020 в 3:36
  • Спасибо за пояснение!
    – W Szum
    2 ноя 2020 в 4:19
  • На некоторые примеры все равно выдает ответ больше на две единицы, чем нужно. Что может быть причиной? try/except?
    – W Szum
    2 ноя 2020 в 5:18

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.