Rectángulo más grande de 1 en 2d matriz binaria

Question

Hay un problema para encontrar el área máxima de 1 en la matriz 0-1. En este problema hay dos casos:

1. área a medir es de forma cuadrada. eso es simple por DP.

2. área a ser medida es de la forma de rectángulo. No puedo pensar una solución óptima para esto.

Ejemplo:

010101 
101001 
111101 
110101 

El rectángulo más grande tiene una superficie de 4 (tercera fila, quinta columna y uno más en tercera, cuarta fila). ¿Podemos obtener todos esos rectángulos?

Answer 1

Yo te paso a través de algunas soluciones de dificultad creciente/decreciente complejidad en tiempo de ejecución.

En primer lugar, una solución de fuerza bruta. Genera todos los rectángulos posibles. Puede hacerlo iterando a través de cada par de puntos (r1, c1) (r2, c2) con r1 ≤ r2 y c1 ≤ c2 (se puede hacer con 4 bucles for). Si un rectángulo no contiene un 0, se compara el área con el área más grande encontrada hasta ahora. Esto es un O (R^3C^3).

Podemos acelerar el cheque rectángulo válida a O (1). Hacemos esto haciendo un DP donde dp (r, c) almacena el número de 0 en el rectángulo ((1, 1), (r, c)).

• dp (r, 0) = 0
• dp (0, c) = 0
• dp (r, c) = dp (r-1, c) + dp (r, c- 1) -dp (r1, c1) + (matriz [r] [c] 0:? 1)

Entonces el número de 0 de en ((r1, c1), (r2, c2)) es

• nzeroes (r1, c1, r2, c2) = dp [R2] [c2] -dp [r1 -1] [c2] -dp [R2] [c1 -1] + dp [ r1 -1] [c1 -1]

A continuación, puede comprobar si un rectángulo es válida por nzeroes (R1, C1, R2, C2) == 0.

Hay un O (R^2C) solución para esto el uso de un DP simple y una pila. El DP funciona por columna, al encontrar el número de 1 celda sobre una celda hasta el próximo 0. El dp es el siguiente:

dp (r, 0) = 0 dp (r, c) = 0 si matriz [r] [c] == 0 dp (r, c) = dp (r-1, c) + 1 en caso contrario

a continuación, hacer lo siguiente:

area = 0 
for each row r: 
    stack = {} 
    stack.push((height=0, column=0)) 
    for each column c: 
    height = dp(r, c) 
    c1 = c 
    while stack.top.height > height: 
     c1 = stack.top.column 
     stack.pop() 
    if stack.top.height != height: 
     stack.push((height=height, column=c1)) 
    for item in stack: 
     a = (c - item.column + 1) * item.height 
     area = max(area, a) 

también es posible resuelva el problema en O (RC) usando tres DP:

• h (r, c): si comenzamos en (r, c) y vamos hacia arriba, ¿cuántas células 1 encontramos antes del primer 0?
• l (r, c): ¿a qué distancia podemos extender un rectángulo con la esquina inferior derecha en (r, c) y la altura h (r, c)?
• r (r, c): ¿hasta qué punto podemos extender un rectángulo con la esquina inferior izquierda en (r, c) y la altura h (r, c)?

Los tres relaciones de recurrencia son:

• h (0, c) = 0
• h (r, c) = 0 si la matriz [r] [c] == 0

• h (r, c) = h (r-1, c) 1 de otro modo

• l (r, 0) = 0

• l (r, c) = cp si matriz [r- 1] [c] == 0

• l (r, c) = min (l (r - 1, c), c - p) de lo contrario

• r (r, C + 1) = 0

• r (r, c) = pc si matriz [r-1] [c] == 0
• r (r, c) = min (r (r - 1, c), PC) de lo contrario

donde p es la columna del 0 anterior a medida que llenamos l de izquierda a derecha yr de derecha a izquierda.

La respuesta es entonces:

• Max_r, c (h (r, c) * (l (r, c) + r (r, c) - 1))

Esto funciona debido a la observación de que el rectángulo más grande siempre tocará un 0 (considerando que el borde está cubierto por 0) en los cuatro lados. Al considerar todos los rectángulos con al menos la parte superior, la izquierda y la derecha tocando un 0, cubrimos todos los rectángulos candidatos. Genera todos los rectángulos posibles. Puede hacerlo iterando a través de cada par de puntos (r1, c1) (r2, c2) con r1 ≤ r2 y c1 ≤ c2 (se puede hacer con 4 bucles for). Si un rectángulo no contiene un 0, se compara el área con el área más grande encontrada hasta ahora.

Nota: Adapté lo anterior de una respuesta que escribí here - consulte la sección "mamá de Ben". En ese escrito, los 0 son árboles. Ese informe también tiene un mejor formato.

Answer 2

me gustaría probar el siguiente:

(1) descomponer la matriz en componentes conectados (a través de BFS).

(2) Para cada componente conectado, busque el rectángulo máxima.

Para hacer (2), primero buscaría rectángulos verticales: Encuentre el ancho máximo posible para cada consecutiva (min_y, max_y), y por lo tanto el área (iterativamente, en O (1) por fila, simplemente mirando en el mínimo/máximo de 1 en esa fila del componente conectado). Luego transpongo la matriz y repito el proceso.

El tiempo total de ejecución es O (MxN) para BFS, luego O (ancho^2 + altura^2) para cada componente conectado, para un total de O (MXN + M^2 + N^2).

Me pregunto cuál es la solución óptima, aunque asintóticamente.

Answer 3

El problema se puede reducir para encontrar el área de rectángulo máxima en un histograma, varias veces.

Después de cada fila, calcula el histograma construido hasta esa fila y calcula el área máxima del rectángulo en ese histograma.

int maximalRectangle(vector<vector<char> > &mat) { 
    int rows=mat.size(); 
    if(rows==0)return 0; 
    int columns = mat[0].size(); 

    int temp[columns]; 
    for(int i=0;i<columns;i++){ 
     temp[i] = mat[0][i]-'0'; 
    } 

    int maxArea=0; 
    maxArea = max(maxArea,maxUtil(temp,columns)); 
    // cout<<"before loop\n"; 
    // print1d(temp,columns); 
    for(int i=1;i<rows;i++){ 
     for(int j=0;j<columns;j++){ 
      temp[j] = (mat[i][j]-'0')?temp[j]+1:0; 
     } 
     // cout<<"after iteration : "<<i<<endl; 
     // print1d(temp,columns); 
     maxArea = max(maxArea,maxUtil(temp,columns)); 
     // cout<<"maxarea = "<<maxArea<<endl; 
    } 
    return maxArea; 
} 

temp es el histograma en cada paso y maxutil calcula el área rectanglular max en que histograma.

Answer 4

** 

//use this dynamic programming approach 
//The problem can be reduced to finding the maximum rectangle area in a histogram, multiple times. 
After each row, you calculate the histogram built until that row, and that calculate the maximum area rectangle in that histogram. 

**

import java.util.Scanner; 


public class LargestRectInAmatrix { 
    static int row,col,matrix[][]; 
    static int maxArea=0; 
    static int barMatrix[]; 
    public static void main(String[] args) { 
     Scanner sc=new Scanner(System.in); 
     row=sc.nextInt(); 
     col=sc.nextInt(); 
     matrix=new int[row][col]; 
     barMatrix=new int[col]; 
     for(int i=0;i<row;i++) 
     { 
      for(int j=0;j<col;j++) 
      { 
       matrix[i][j]=sc.nextInt(); 
      } 
     } 
     startSolution(); 
     System.out.println(maxArea); 

    } 
    private static void startSolution() 
    { 
     for(int i=0;i<row;i++) 
     { 
      for(int j=0;j<col;j++) 
      { 
      if(matrix[i][j]==0) 
      { 
       barMatrix[j]=0; 
      } 
      else 
       barMatrix[j]=barMatrix[j]+matrix[i][j]; 
      } 
      int area=calculateArea(0,col-1); 
      if(area>maxArea) 
      { 
       maxArea=area; 
      } 
     } 

    } 
    private static int calculateArea(int l,int h) 
    { 
     if(l>h) 
     { 
      return Integer.MIN_VALUE; 
     } 
     if(l==h) 
     { 
      return barMatrix[l]; 
     } 
     int u=calMinimumIndex(l,h); 
     return (max(calculateArea(l, u-1),calculateArea(u+1, h),barMatrix[u]*(h-l+1))); 



    } 
    private static int max(int a,int b,int c) 
    { 
     if(a>b) 
     { 
      if(a>c) 
      { 
       return a; 
      } 
      else 
       return c; 
     } 
     else 
      if(b>c) 
      { 
       return b; 
      } 
      else 
       return c; 
    } 
    private static int calMinimumIndex(int l,int h) 
    { 
     int min=Integer.MAX_VALUE; 
     int min_index=0; 
     for(int i=l;l<=h;i++) 
     { 
      if(barMatrix[i]<min){ 
       min=barMatrix[i]; 
       min_index=i; 
      } 
     } 
     return min_index; 
    } 


} 

Answer 5

Otro enfoque más sencillo es utilizar dos temp M x N matrices para calcular la longitud de rectángulos (fila y columna en cuanto a) - es decir, recuento de consecutivo 1 de a continuación. Atraviese las dos matrices de temperatura para encontrar las longitudes de repetición máximas (filas y columnas).

Aquí está el código para el mismo.

int GetMaxRectangularArea(vector<vector<int>> & matrix, int nRows, int nCols) 
{ 
    vector<vector<int>> rowLengths(nRows, vector<int>(nCols)); 
    vector<vector<int>> colLengths(nRows, vector<int>(nCols)); 

    // initialize first column of rowLengths with first column of matrix 
    for (int i = 0; i < nRows; i++) { 
     rowLengths[i][0] = matrix[i][0]; 
    } 

    // initialize first row of colLengths with first row of matrix 
    for (int j = 0; j < nCols; j++) { 
     colLengths[0][j] = matrix[0][j]; 
    } 

    // Compute row wise length of consecutive 1's in rowLengths 
    for (int i = 0; i < nRows; i++) { 
     for (int j = 1; j < nCols; j++) { 
      if (matrix[i][j] == 1) { 
       rowLengths[i][j] = 1 + rowLengths[i][j - 1]; 
      } 
      else { 
       rowLengths[i][j] = 0; 
      } 
     } 
    } 

    // Compute column wise length of consecutive 1's in colLengths 
    for (int j = 0; j < nCols; j++) { 
     for (int i = 1; i < nRows; i++) { 
      if (matrix[i][j] == 1) { 
       colLengths[i][j] = 1 + colLengths[i- 1][j]; 
      } 
      else { 
       colLengths[i][j] = 0; 
      } 
     } 
    } 

    // Now traverse the rowLengths array to find max length sub array 
    int maxArea = 0; 

    for (int j = nCols - 1; j >= 0; j--) { 
     int currentArea = 0; 
     int currentMax = -1; 
     int repeats = 1; 

     for (int i = nRows - 1; i >= 0; i--) { 
      if (rowLengths[i][j] != currentMax) { 
       if (currentMax != -1) { 
        currentArea = currentMax * repeats; 

        if (currentArea > maxArea) { 
         maxArea = currentArea; 
        } 
       } 

       currentMax = rowLengths[i][j]; 
       repeats = 1; 
      } 
      else { 
       repeats++; 
      } 
     } 

     currentArea = currentMax * repeats; 

     if (currentArea > maxArea) { 
      maxArea = currentArea; 
     } 
    } 

    for (int i = nRows - 1; i >= 0; i--) { 
     int currentArea = 0; 
     int currentMax = -1; 
     int repeats = 1; 

     for (int j = nCols - 1; j >= 0; j--) { 
      if (colLengths[i][j] != currentMax) { 
       if (currentMax != -1) { 
        currentArea = currentMax * repeats; 

        if (currentArea > maxArea) { 
         maxArea = currentArea; 
        } 
       } 

       currentMax = colLengths[i][j]; 
       repeats = 1; 
      } 
      else { 
       repeats++; 
      } 
     } 

     currentArea = currentMax * repeats; 

     if (currentArea > maxArea) { 
      maxArea = currentArea; 
     } 
    } 

    return maxArea; 
} 

Answer 6

class GfG{ 
    public int maxArea(int a[][],int m,int n){ 
     if(a==null || m==0 || n== 0) return 0; 
     m = a.length; 
     n = a[0].length; 
     int dp[] = new int[n+1]; 
     int height[] = new int[n]; 
     int p = 0; 
     dp[p] = -1; 
     int ans = 0; 
     //System.out.println("1 "); 
     for(int i = 0;i<m;i++){ 
      for(int j = 0;j<n;j++){ 
       if(a[i][j]==1){ 
        height[j] += a[i][j]; 
       } 
       else{ 
        height[j] = 0; 
       } 
      } 
      p= 0; 
      //System.out.println("2 "); 
      for(int j = 0;j<n;j++){ 
       while(p>0 && height[j] < height[dp[p]]){ 
        int start = dp[p-1]; 
        ans = Math.max(ans,(j-start-1)*height[dp[p]]); 
        p--; 
        //System.out.println("1 "); 
       } 
       dp[++p] = j; 
      } 
     } 
     return ans; 
    } 
}