Matriz de área mínima que cubre

Question

Considerando una matriz binaria n-por-n, me gustaría encontrar el área mínima de dos rectángulos que cubriría todas las (1s). Es decir, la suma de las áreas de los rectángulos debe ser mínima. Los rectángulos se pueden superponer.

Ejemplo:

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 

El área mínima es: 3 * 9 + 9 * 3 = 54

estoy interesado en saber si hay una solución mejor que O(n^4).

Answer 1

Primero puede resolver el problema para un rectángulo encontrando los 1s más altos, más bajos, más a la derecha y más a la izquierda de la matriz. Entonces sabrá que puede mejorar su resultado utilizando un segundo rectángulo si y solo si puede cortar los trozos simétricos de todos los 0.