Здравствуйте Painkiller, Вы писали:

P>есть фигура на клетчатой бумаге (фактически, двумерный массив из 0 и 1)
P>задача: разбить ее на минимальное количество непересекающихся клеточных прямоугольников

P>формулируется просто, но как решать?
Есть какие-то ещё ограничения, например, сложность алгоритма, сложность дальнейшего поиска, отношение ширины к высоте, прямоугольники примерно одинакового размера и пр. Нужен ли абсолютный минимум, или же задача формулируется разбить на желательно наименьшее количество прямоугольников?

Пока пришло в голову следующее (минимум не гарантирую):
Инициализация:

Каждая заполненная клетка становится прямоугольником.

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

Заместить оба прямоугольника на один.

Можно в цикле выбирать по критериям, например, выбирать такое сочетание, которое максимально увеличит площадь.

Вопрос: это как-то связано с картами Карно??? В любом случае, поищи сабж, должно помочь...

ЗЫ: Утро, голова не варит...