Здравствуйте Painkiller, Вы писали:
P>есть фигура на клетчатой бумаге (фактически, двумерный массив из 0 и 1) P>задача: разбить ее на минимальное количество непересекающихся клеточных прямоугольников
P>формулируется просто, но как решать?
Ищем углы прямоугольников — точки у которых соседи слева и сверху или слева и снизу имеют другой цвет. Проводи через них прямые и получаем набор прямоугольников. Не минимальный но всеже — потом решаем задачу их объединения — тут уже много вариантов. Например — находим центры прямоугольников — строим граф — соединяем только те вершины которые лежать на одной вертикали или горизонтали. И ищем наибольший цикл (или просто циклы) — находим удаляем. И объединяем те прямоугольники центры которых входят в цикл. И так далее. потом соединяем оставщиеся прямые.
Можно более просто построить граф по всем точкам и опять же искать циклы.
ИМХО должно работать но ручаться не буду.
P.S. Пмниться была эта задачка на одном из туров Московской олимпиады.
