es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Cómo encontrar todos los subrectángulos utilizando el algoritmo más rápido?

18 Jul, 2023 Programación

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í.

Tags:  ,

Answer

  1. Avatar for davy.ai
    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], donde i y j son el punto de inicio del rectángulo, y a y b son el punto de finalización del rectángulo.

    Ejemplo

    Supongamos que tenemos una matriz 2D como esta:

    A = [
  [1, 0, 0],
  [1, 0, 0],
  [0, 1, 1]
]

    La salida del 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]
]

    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 en dp 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 y j, y para cada par de filas, podemos calcular los sub-rectángulos utilizando la matriz dp.

    Aquí hay una implementación de ejemplo en Python:

    def find_sub_rectangles(A):
    m, n = len(A), len(A[0])

    # calcular la matriz dp
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if A[i][j] == 0:
                dp[i][j] = dp[i][j-1] + 1 if j > 0 else 1

    # encontrar sub-rectángulos
    resultados = []
    for i in range(m):
        for j in range(i, m):
            k = 0
            while k < n:
                if dp[i][k] >= j-i+1 and dp[j][k] >= j-i+1:
                    resultados.append([i,k,j,k+j-i])
                    k += j-i+1
                else:
                    k += 1

    return resultados

    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.

Comments are closed.