Получить максимально возможный экстент для прямоугольника в данном пространстве с препятствиями

Question

Я имею дело со следующей проблемой:

Есть сетка с пустыми ячейками (пустые ячейки показаны белым).Отдельные ячейки в этой сетке уже «заняты» элементами (элементы показаны оранжевым цветом).

Теперь у меня есть начальная точка прямоугольника (в данном случае строка 6, столбец 3).Этот прямоугольник должен занимать как можно больше свободных ячеек.Прямоугольник должен останавливаться на оранжевых элементах или когда сетка заканчивается.

Прикрепленный снимок экрана показывает 2 сценария сетки и их решения.

Левый сценарий вернет

width = 2
height = 5

Правильный сценарий вернул бы

width = 1
height = 5

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

Есть ли чистое, короткое математическое решение для этого, или это простая проблема, которая не так проста, как кажется на первый взгляд?

Спасибо..

Answer 1

Представляет сетку с помощью матрицы 0-1, где 1 соответствует препятствию.

Если сетка имеет значение m x n, а (a,b) - это основанные на 0 индексы строк и столбцовначальная ячейка, тогда width = n-b представляет максимально возможную ширину прямоугольника, начинающегося в этой ячейке, независимо от каких-либо препятствий.Это текущая ширина.Теперь начните сканировать столбец из этой ячейки, пока не встретите нижний край или препятствие.Для каждой ячейки в этом столбце начинайте сканирование вправо, пока не будет достигнуто препятствие или текущая ширина.Если препятствие встречается первым, уменьшите текущую ширину.Добавьте текущую ширину к списку ширин (независимо от того, была ли уменьшена текущая ширина).

На этом этапе у вас есть список ширин, с одной шириной для каждой потенциальной высоты.Просто просканируйте этот список, умножив каждую ширину на соответствующую высоту (которая будет равна 1 + индекс списка на основе 0).Верните пару (высота, ширина), которая максимизировала высоту продукта * ширина.

Реализация Python:

def find_max_rect(grid,a,b):
    if grid[a][b] == 1: return (0,0)
    m = len(grid) #number of rows
    n = len(grid[0]) #number of columns
    width = n-b #maximum possible width given starting column
    widths = [] 
    i = a
    while i < m and grid[i][b] == 0:
        #scan right from (i,b+1) until a 1 or current width is hit
        for j in range(b+1,b+width):
            if grid[i][j] == 1:
                #an obstacle forces width to contract
                width = j-b #number of steps before obstacle
                break #out of inner loop
        widths.append(width)
        i += 1      
    max_area = 0
    max_at = -1
    for i,width in enumerate(widths):
        if (i+1)*width > max_area:
            max_area = (i+1)*width
            max_at = i
    return (max_at + 1,widths[max_at])

Проверено как:

test_grid = [[1,0,1,1,0],
             [0,1,0,0,0],
             [0,1,0,0,0],
             [0,1,0,0,0],
             [0,0,0,1,0],
             [0,0,0,1,0],
             [0,0,0,0,1],
             [0,0,0,0,0],
             [1,0,0,0,0],
             [0,0,0,0,1],
             [0,1,0,0,0]]

print(find_max_rect(test_grid,6,2)) #prints (5,2)

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

def find_max_rect(grid,a,b):
    if grid[a][b] == 1: return (0,0)
    m = len(grid) #number of rows
    n = len(grid[0]) #number of columns
    current_height = 0
    current_width = n - b #maximum possible width given starting column
    max_area = 0
    best_height, best_width = current_height, current_width

    i = a
    while i < m and grid[i][b] == 0:
        current_height += 1
        #scan right from (i,b + 1) until a 1 or current width is hit
        for j in range(b + 1,b + current_width):
            if grid[i][j] == 1:
                #an obstacle forces width to contract
                current_width = j - b #number of steps before obstacle
                break
        #decide if the best should be adjusted
        current_area = current_height * current_width
        if  current_area > max_area:
            best_area, best_height, best_width = current_area, current_height, current_width
        i+=1
    return best_height, best_width