Постановка задачи: Существует картинка - прямоугольник со сторонами N и M, изначально составленная из элементарных квадратов (1x1). Каждый квадрат имеет свойство:цвет. Квадраты в прямоугольнике расположены как ячейки в таблице (другая аналогия: картинка и её пиксели). Я пытаюсь написать/найти алгоритм, который уменьшает общее кол-во (а лучше - находит минимум) квадратов, "склеивая" их в прямоугольники (конструкции вида Г или Т создавать нельзя). Условие склеивания: одинаковый цвет. Т.е. чем из меньшего числа прямоугольников и квадратов будет в конце состоять наша "картинка", тем лучше. Понятно что найдутся неоптимизирующиеся прямоугольники:
Простейший алгоритм: пробежаться в цикле построчно (или по столбцам) и "склеивать" соседей, если они одноцветны. Но мне почему-то кажется, что существует "двумерный" алгоритм (из квадратов образуются как горизонтальные так и вертикальные прямоугольники). Его и пытаюсь найти
Вопрос: Может кто знает название подобного алгоритма (или ссылку на аналогичное)? Заранее спасибо
