Cómo encontrar todos los subrectángulos utilizando el algoritmo más rápido?
Un ejemplo, supongamos que tenemos una matriz 2D como esta:
A= [
[1,0,0],
[1,0,0],
[0,1,1]
]
La tarea es encontrar todos los subrectángulos que concluyan solo en ceros. Por lo tanto, la salida de este algoritmo debería ser:
[[0,1,0,2] , [0,1,1,1] , [0,2,1,2] , [0,1,1,2] ,[1,1,1,2], [2,0,2,0] ,
[0,1,0,1] , [0,2,0,2] , [1,1,1,1] , [1,2,1,2]]
Donde i,j en [i,j,a,b]
son las coordenadas del punto de inicio del rectángulo y a,b son las coordenadas del punto final del rectángulo.
Encontré algunos algoritmos, por ejemplo Link1 y Link2, pero creo que el primero es el algoritmo más simple y queremos el más rápido. En el segundo, vemos que el algoritmo solo calcula rectángulos y no todos los subrectángulos.
Pregunta:
¿Alguien conoce un algoritmo mejor o más rápido para este problema? Mi idea es usar programación dinámica, pero cómo utilizarla no es fácil para mí.
davy.ai
Encontrar sub-rectángulos que solo contienen ceros
Declaración del problema
Dada una matriz 2D, la tarea es encontrar todos los sub-rectángulos que solo contengan ceros. La salida del algoritmo debe ser una lista de coordenadas en formato
[i, j, a, b]
, dondei
yj
son el punto de inicio del rectángulo, ya
yb
son el punto de finalización del rectángulo.Ejemplo
Supongamos que tenemos una matriz 2D como esta:
La salida del algoritmo debería ser:
Solución
Una forma de resolver este problema es a través de la programación dinámica. Podemos usar una matriz 2D
dp
para realizar un seguimiento del número de ceros consecutivos en cada fila. Cada celda endp
contendrá el número de ceros consecutivos en la fila correspondiente hasta ese punto.Para encontrar los sub-rectángulos, podemos iterar sobre todos los pares posibles de filas de inicio y final
i
yj
, y para cada par de filas, podemos calcular los sub-rectángulos utilizando la matrizdp
.Aquí hay una implementación de ejemplo en Python:
La complejidad temporal de este algoritmo es O(m^2 * n), donde m es el número de filas y n es el número de columnas en la matriz de entrada.