Получение всех возможных прямоугольников из массива точек (любой язык)

[sancho123]

Доброго времени суток!
Я уже давно не студент. Просто не нашел раздела для алгоритмов.
Есть матрица из 0 и 1.
0 - свободная точка.
1 - занятая точка.

Нужно найти все возможные прямоугольники.
Прямоугольники должны покрывать всю пустую область (она образована нулями) и могут пересекаться, но не должны быть друг в друге.

Результат нужно записать в массив записей:
X,Y,W,H (строка, столбец, ширина, высота).

Пример:
00000
00000
10100
10100

Результат:
0,0,5,2
1,0,1,4
3,0,2,4

В графическом виде


Возможен ли параллельный алгоритм?
Если нет, буду рад любому работающему алгоритму на любом языке программирования.
Желательно С#.

[s-andriano]

Непонятно как условие, так и решение.
На мой взгляд условию "Прямоугольники должны покрывать всю пустую область" удовлетворяет один единственный прямоугольник - размером со всю область. Других прямоугольников, удовлетворяющих этому условию, нет.
Непонятно в каком виде записано решение. Что означают эти цифры?

[sancho123]

Да. Немного поспешил. Исправил ошибки в первом сообщении.

[s-andriano]

так что нужно получить на выходе?
Чем не устраивает вариант с единственным прямоугольником, покрывающим всю область?
Среди прямоугольников, приведенных в решении, нет ни одного, который бы удовлетворял условию задачи. Как это понимать?

[sancho123]

Сообщение от s-andriano

так что нужно получить на выходе?
Чем не устраивает вариант с единственным прямоугольником, покрывающим всю область?
Среди прямоугольников, приведенных в решении, нет ни одного, который бы удовлетворял условию задачи. Как это понимать?

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

На рисунке их 3.
Серым изобразил занятые области. Все остальное - свободная область.

"Прямоугольники должны покрывать всю пустую область"
Напишу иначе:
Нужно покрыть свободную область прямоугольниками так, чтобы в ней не осталось свободных(незанятых) точек.

[s-andriano]

Сообщение от sancho123

Напишу иначе:
Нужно покрыть свободную область прямоугольниками так, чтобы в ней не осталось свободных(незанятых) точек.

Это совершенно другое условие.

И как понимать это?

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

Нужно найти все возможные варианты покрытия?

[sancho123]

"Нужно найти все возможные варианты покрытия?"

Да. Спасибо за помощь в формулировании условия