ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      31 Jul 2002  18:31:56
 To : Sergei Makarov
 Subject : Разбиение битовой карты
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Sergei Makarov to All:
 
  SM> Посоветуйте алгоритм решения задачи:
  SM> Дана битовая карта (0|1) N x M.
  SM> Hадо выделить из нее список прямоугольников единиц (структура RECT).
  SM> Критерии оптимальности:     минимум прямоугольников
 
 Первое, что пришло в голову:
 
 1) Hаходишь еще непокрытую "угловую" (см. ниже) единицу, определяешь
 прямоугольник 1x1 из нее состоящий. Если такой единицы нет - конец.
 
 2) Раздуваешь прямоугольник, пока возможно: если снаружи вдоль какой-то стороны 
 стоят одни единицы, добавляешь их к прямоугольнику.
 
 3) Добавляешь прямоугольник в список. Помечаешь все единицы, которые он
 содержит, как покрытые.
 
 4) goto 1
 
 ЗЫ. "Угловая" единица - это единица не зажатая двумя другими непокрытыми
 единицами (по вертикали или горизонтали). Возможные варианты с точностью до
 поворотов:
 
     [*]            [*]         [*]
  [*](1)[*]      [*](1)[1]   [*](1)[1]
     [*]            [*]         [1]
 
 здесь: (1) - угловая единица
        [1] - непокрытая единица
        [*] - ноль, покрытая единица или отсутствие клетки
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.8
  * Origin:  (2:5015/60)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Разбиение битовой карты   Sergei Makarov   31 Jul 2002 09:32:58   Разбиение битовой карты   Max Alekseyev   31 Jul 2002 18:31:56   Re: Разбиение битовой карты   Sergey Radkevich   02 Aug 2002 12:30:37