Największy prostokąt 1 w 2d macierzy dwójkowej

Question

Występuje problem z znalezieniem maksymalnego obszaru 1 w macierzy 0-1. W tym problemie występują dwa przypadki:

1. powierzchnia do zmierzenia ma kształt kwadratu. to proste dzięki DP.

2. Obszar do pomiaru ma kształt prostokąta. nie jestem w stanie znaleźć optymalnego rozwiązania.

przykład:

010101 
101001 
111101 
110101 

Największy prostokąta o powierzchni 4 (3 rząd, 5 kolumny i jeden w 3, 4 wiersz). Czy możemy również uzyskać wszystkie te prostokąty?

Answer 1

Przechodzę przez kilka rozwiązań zwiększających trudności/zmniejszających złożoność środowiska wykonawczego.

Po pierwsze, rozwiązanie brutalnej siły. Wygeneruj każdy możliwy prostokąt. Możesz to zrobić przez powtarzanie każdej pary punktów (r1, c1) (r2, c2) z r1 ≤ r2 i c1 ≤ c2 (można zrobić z 4 dla pętli). Jeśli prostokąt nie zawiera wartości 0, porównujesz obszar do największego znalezionego do tej pory obszaru. To jest O (R^3C^3).

Możemy przyspieszyć prawidłowe sprawdzanie prostokąta do O (1). Robimy to, wykonując DP, w którym dp (r, c) przechowuje liczbę 0 w prostokącie ((1, 1), (r, c)).

• DP (r, 0) = 0
• DP (0 C) = 0
• DP (R c) DP = (R-1 c) + DP (R, C 1) -dp (r-1, c-1) + (macierz [r] [c] 0: 1)

Następnie liczba 0 w ((r1, c1), (r2, c2)) jest

• nzeroes (R1, C1, R2, C2) = Dp [r2] [C2] -DP [r1 -1], [C2] -DP [R2] [C1 -1] + [DP r1 -1] [c1 -1]

Następnie można sprawdzić, czy prostokąt jest ważny przez nozniki (r1, c1, r2, c2) == 0.

Istnieje rozwiązanie O (R^2C) do tego przy użyciu prostego DP i stosu. DP działa na kolumnę, znajdując liczbę 1 komórek powyżej komórki do następnego 0. Wartość dp jest następująca:

dp (r, 0) = 0 dp (r, c) = 0, jeśli macierz [R], [c] == 0 DP (R c) (R = DP-1, c) + 1 poza

wtedy należy wykonać następujące czynności:

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) 

jest również możliwe, aby rozwiązać problem w O (RC) za pomocą trzech DP:

• h (r, c): jeśli zaczniemy od (r, c) i pójdziemy w górę, ile 1 komórek znajdziemy przed pierwszymi 0?
• l (r, c): jak daleko możemy rozciągnąć prostokąt z dolnym prawym rogiem na (r, c) i wysokości h (r, c)?
• r (r, c): jak daleko na prawo możemy rozciągnąć prostokąt z dolnym lewym rogiem na (r, c) i wysokości h (r, c)?

Trzy stosunki nawrotów:

• H 0 (c) = 0
• H (R, C) = 0, jeżeli macierz [R], [c] == 0

• h (R, C) = h (r-1 C) +1 inaczej

• l (r, 0) = 0

• l (R, C) = CP jeśli matryca [r- 1] [c] == 0

• l (R, C) = min (l (R - 1, c), c - p) poza

• R (R, C + 1) = 0

• R (r, c) = pc, jeśli matryca [r-1], [c] == 0
• R (R, C) = min (R (R - 1, c), PC) poza

gdzie p jest kolumną poprzedniego 0, gdy wypełniamy l od lewej do prawej i r od prawej do lewej.

Odpowiedź wynosi:

• max_r C (H (r, c) * (l (R c) + R (R c) - 1))

Działa to z powodu obserwacji, że największy prostokąt zawsze dotyka 0 (biorąc pod uwagę krawędź jako pokryty w 0) na wszystkich czterech bokach. Rozważając wszystkie prostokąty z co najmniej górną, lewą i prawą powierzchnią dotykając 0, pokrywamy wszystkie kandydujące prostokąty. Wygeneruj każdy możliwy prostokąt. Możesz to zrobić przez powtarzanie każdej pary punktów (r1, c1) (r2, c2) z r1 ≤ r2 i c1 ≤ c2 (można zrobić z 4 dla pętli). Jeśli prostokąt nie zawiera wartości 0, porównujesz obszar do największego znalezionego do tej pory obszaru.

Uwaga: dostosowałem powyższą odpowiedź z odpowiedzi, którą napisałem: here - patrz rozdział "Mama Bena". W tym zapisie 0 to drzewa. Ten zapis ma również lepsze formatowanie.

Answer 2

ja spróbuj:

(1) Rozłożenie matrycę do połączonych składników (przez BFS).

(2) Dla każdego podłączonego komponentu znajdź maksymalny prostokąt.

Do zrobienia (2), najpierw szukam pionowych prostokątów: znajdź maksymalną możliwą szerokość dla każdego kolejnego (min_y, max_y), a tym samym obszar (iteracyjnie, w O (1) na wiersz, po prostu patrząc przy min/max 1 w tym wierszu podłączonego komponentu). Następnie przetransponowałbym macierz i powtórzyć proces.

Całkowity czas działania to O (MxN) dla BFS, a następnie O (szerokość^2 + wysokość^2) dla każdego podłączonego podzespołu, dla łącznej liczby O (MXN + M^2 + N^2).

Zastanawiam się, jakie jest jednak optymalne asymptotycznie rozwiązanie.

Answer 3

Problem można zmniejszyć do wielokrotnego znalezienia maksymalnego obszaru prostokąta na histogramie.

Po każdym wierszu oblicza się histogram zbudowany do tego wiersza i oblicza maksymalny prostokąt obszaru na tym histogramie.

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 jest histogram w każdym etapie i maxutil oblicza maksymalny obszar rectanglular w tym histogramem.

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

Innym prostszym sposobem jest użycie dwóch macierzy temp MxN obliczenie długości prostokąta (wiersz i kolumnę bit) - czyli liczba kolejnych 1-czasu. Przetestuj dwie matryce temp, aby znaleźć maksymalne długości powtarzania (mądre wiersze i kolumny).

Oto kod dla tego samego.

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; 
    } 
}