Алгоритм группировки клеток в прямоугольники

Question

Представьте, что рисунок выше представляет массив 6 * 6 целых, где 0 - черный. Существует ли быстрый алгоритм для разделения не 0 ячеек на прямоугольники? В идеале проверка должна содержаться в цикле for без создания каких-либо других массивов .

for(x = 0; x < 6; x++)
    for(y = 0; y < 6; y++)
        if(cellIsBottomRightOfRect(x,y)) {
            left = getLeft(x,y);
            top = getTop(x,y);
            printf("Rect: %d,%d %d,%d \n", left, top, x, y);
        }

Answer 1

Как насчет использования рекурсивного метода, который вызывает себя каждый раз, когда встречает цвет, отличный от того, который он пытается сгруппировать в данный момент?

Answer 2

Задумывались ли вы об использовании подхода динамического программирования ?

Кроме того, я думаю, что алгоритм поиска (например, A *) будет хорошо работать здесь (даже если он имеет экспоненциальное время).сложность).