Покрытие матрицы минимальной площади

Question

Рассматривая двоичную матрицу n-на-n, я хотел бы найти минимальную площадь из двух прямоугольников, которая охватывала бы все из них (1 с). То есть сумма площадей прямоугольников должна быть минимальной. Прямоугольники могут перекрываться.

Пример:

0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0

Минимальная площадь: 3 * 9 + 9 * 3 = 54

Мне интересно знать, есть ли решение лучше, чем O(n^4).

Answer 1

Вы можете сначала решить проблему для одного прямоугольника, найдя самые верхние, самые нижние, самые правые и самые левые 1 в матрице. Тогда вы знаете, что вы можете улучшить свой результат, используя второй прямоугольник, если и только если вы можете вырезать симметричные куски всех 0.