encontrar todas las áreas rectangulares con ciertas propiedades en una matriz

Question

dado un m matriz n * con los posibles valores de 1, 2 y null:

. . . . . 1 . . 
    . 1 . . . . . 1 
    . . . 2 . . . . 
    . . . . 2 . . . 
    1 . . . . . 1 . 
    . . . . . . . . 
    . . 1 . . 2 . . 
    2 . . . . . . 1 

Estoy buscando para todos los bloques B (que contienen todos los valores entre (x0, y0) y (x1, y1)) que:

• contienen al menos un '1'
• no contienen '2'
• no son un subconjunto de un otro bloque con las propiedades anteriores

Ejemplo:

El área roja, verde y azul todos contienen un '1', no '2', y no son parte de un área más grande. Por supuesto, hay más de 3 bloques en esta imagen. Quiero encontrar todos estos bloques.

¿cuál sería una forma rápida de encontrar todas estas áreas?

Tengo una solución de fuerza bruta en funcionamiento, iterando sobre todos los rectángulos posibles, comprobando si cumplen los dos primeros criterios; luego iterando sobre todos los rectángulos encontrados, eliminando todos los rectángulos que están contenidos en otro rectángulo; y puedo acelerar eso eliminando primero filas y columnas idénticas consecutivas. Pero estoy bastante seguro de que hay una manera mucho más rápida.

Answer 1

Finalmente encontré una solución que funciona casi en tiempo lineal (hay un pequeño factor que depende del número de áreas encontradas). Creo que esta es la solución más rápida posible.

Inspirado por esta respuesta: https://stackoverflow.com/a/7353193/145999 (imágenes también se tomaron de allí)

En primer lugar, voy trought la matriz de la columna, la creación de una nueva matriz M1 medir el número de pasos a la última '1' y una matriz M2 medir el número de pasos a la última '2'

Imaginemos un '1' o '2' en cualquiera de los bloques grises en la imagen superior

al final tengo M1 y M2 mirando como este:

Sin pasar por M1 y M2 a la inversa, por fila:

ejecuto el siguiente algoritmo:

foundAreas = new list() 

For each row y backwards: 
    potentialAreas = new List() 
    for each column x: 
     if M2[x,y]>M2[x-1,y]: 
      add to potentialAreas: 
       new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false) 
     if M2[x,y]<M2[x-1,y]: 
      for each area in potentialAreas: 
       if area.hasTop and area.hasOne<area.height: 
         add to foundAreas: 
          new Box(Area.left,y-area.height,x,y) 
      if M2[x,y]==0: delete all potentialAreas 
      else: 
       find the area in potentialAreas with height=M2[x,y] 
       or the one with the closest bigger height: set its height to M2[x,y] 
       delete all potentialAreas with a bigger height 

      for each area in potentialAreas: 
       if area.hasOne>M1[x,y]: area.hasOne=M1[x,y] 
       if M2[x,y+1]==0: area.hasTop=true 

ahora foundAreas contiene todos los rectángulos con las propiedades deseadas .

Answer 2

Puede encontrar un lugar entre cada rectángulo y una solución inteligente.

Por ejemplo, a partir de cada 1 puede crear un rectángulo y expandir gradualmente sus bordes hacia afuera en 4 direcciones. Deténgase cuando golpee un 2, grabe este rectángulo si (a) ha tenido que detenerse en las 4 direcciones, y (b) no ha visto este rectángulo antes.

Luego retroceda: debe ser capaz de generar tanto el rectángulo rojo como el rectángulo verde a partir del 1 cerca de la esquina superior izquierda.

Sin embargo, este algoritmo tiene algunos peores peores casos. Una entrada que consta de todos los resortes 1 s a la mente. Por lo tanto, necesita combinarse con alguna otra habilidad o algunas restricciones en la entrada.

Answer 3

Considere el problema más simple una dimensión:

Encuentra todas las subcadenas de .2.1.1...12....2..1.1..2.1..2 que contiene al menos un 1 y sin 2 y no son subcadena de dicha cadena. Esto se puede resolver en tiempo lineal, solo tiene que verificar si hay un 1 entre dos 2.

ya se puede adaptar fácilmente este algoritmo para el problema de dos dimensiones:

Para 1≤i≤j≤n suma de todas las líneas de i a j utilizando la siguiente ley: .+.=., .+1=1, .+2=2, 1+1=1, 1+2=2, 2+2=2 y aplican el algoritmo de dimensión a la línea resultante.

Complejidad: O (n²m).