Каков наиболее эффективный алгоритм для поиска прямоугольника с наибольшей площадью, которая будет помещаться в пустое пространство?
Скажем, экран выглядит следующим образом ('#' представляет заполненную область):
....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............
Вероятное решение:
....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...
Обычно мне понравилось бы выработать решение. Хотя на этот раз я бы хотел не тратить время на то, чтобы поиграть самостоятельно, так как это имеет практическое применение для проекта, над которым я работаю. Существует ли известное решение?
Shog9 написал:
Является ли ваш вход массивом (как подразумевается другими ответами) или списком окклюзий в форме произвольного размера, расположенных прямоугольников (как это может иметь место в системе оконного оформления при работе с положениями окна)?
Да, у меня есть структура, которая отслеживает набор окон, размещенных на экране. У меня также есть сетка, которая отслеживает все области между каждым краем, независимо от того, пусты ли они или заполнены, и положение пикселя их левого или верхнего края. Я думаю, что есть некоторая модифицированная форма, которая воспользуется этим свойством. Вы знаете что-нибудь?