Plus grand rectangle de 1 en 2d matrice binaire

Je vais étape par le biais de quelques solutions de difficulté croissante /décroissante d'exécution de la complexité.

Tout d'abord, une attaque par force brute solution. Générer chaque rectangle possible. Vous pouvez le faire en parcourant chaque paire de points (r1,c1), (r2,c2) avec r1 ≤ r2 et c1 ≤ c2 (peut être fait avec 4 boucles for). Si un rectangle ne contient pas de 0, vous comparez la zone de la plus grande zone trouvée jusqu'à présent. C'est un O(R^3C^3).

Nous pouvons accélérer le rectangle valide vérifier à O(1). Pour ce faire, nous faire une DP où dp(r, c) stocke le nombre de 0 dans le rectangle ((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)+(matrice[r][c]?0:1)

Puis le nombre de 0 dans ((r1, c1), (r2, c2)) est

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

Vous pouvez ensuite vérifier si un rectangle est valide par nzeroes(r1,c1,r2,c2) == 0.

Il y a un O(R^2C) solution pour cela à l'aide d'un simple DP et une pile. Le DP fonctionne par colonne, en trouvant les 1 nombre de cellules au-dessus d'une cellule jusqu'à la prochaine 0. Le dp est comme suit:

dp(r, 0) = 0
dp(r, c) = 0 si la matrice[r][c] == 0
dp(r, c) = dp(r-1, c) + 1 sinon

Vous procédez de la façon suivante:

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)

Il est également possible de résoudre le problème en temps O(RC) à l'aide de trois DP:

• h(r, c): si nous commençons à (r, c) et aller vers le haut, combien de cellules 1-nous trouver avant le premier 0?
• l(r, c): comment l'extrême gauche, pouvons-nous étendre un rectangle dont le coin inférieur droit (r, c) et de la hauteur h(r, c)?
• r(r,c): quel droit pouvons-nous étendre un rectangle avec coin inférieur gauche à (r, c) et de la hauteur h(r, c)?

Les trois relations de récurrence:

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

• h(r, c) = h(r-1, c)+1 sinon

• l(r, 0) = 0

• l(r, c) = c-p si la matrice[r-1][c] == 0

• l(r, c) = min(l(r − 1, c), c − p) sinon

• r(r,C+1) = 0

• r(r,c) = p-c si la matrice[r-1][c] == 0
• r(r,c) = min(r(r − 1, c), p − c) autrement

où p est la colonne de la précédente 0 comme nous remplir de l de gauche à droite et de r de droite à gauche.

La réponse est alors:

• max_r,c(h(r, c) ∗ (l(r, c) + r(r, c) − 1))

Cela fonctionne en raison de l'observation que le plus grand rectangle sera toujours toucher un 0 (en considérant le bord comme étant couverts à 0) sur les quatre côtés. En considérant tous les rectangles avec, au moins, en haut, à gauche et à droite de toucher un 0, nous couvrons tous les rectangles. Générer chaque rectangle possible. Vous pouvez le faire en parcourant chaque paire de points (r1,c1), (r2,c2) avec r1 ≤ r2 et c1 ≤ c2 (peut être fait avec 4 boucles for). Si un rectangle ne contient pas de 0, vous comparez la zone de la plus grande zone trouvée jusqu'à présent.

Remarque: j'ai adapté le au-dessus d'une réponse que j'ai écrit jusqu'à ici - reportez-vous à la section "Ben Maman". Dans cet article, les 0 sont des arbres. Que l'article présente également une meilleure mise en forme.

OriginalL'auteur marcog

Je voudrais essayer le suivant:

(1) Décomposer la matrice dans les composants raccordés (par BFS).

(2) Pour chaque composante connexe, regardez pour les maximales rectangle.

(2), je voudrais tout d'abord verticale rectangles: Trouver le maximum possible de la largeur de chaque consécutives (min_y, max_y), et par conséquent, le domaine (de manière itérative, en O(1) par ligne, juste en regardant les min/max de 1 dans la ligne de l'appareil connecté).
Alors je voudrais transposer la matrice, et répétez le processus.

Le temps total d'exécution est O(MxN) pour BFS, alors O(largeur^2 + hauteur^2) pour chaque composante, pour un total de O(MXN + M^2 + N^2).

Je me demande quelle est la asymptotiquement optimale de la solution.

OriginalL'auteur Guy Adini

Une autre approche la plus simple consiste à utiliser deux temp de M x N de tableaux pour calculer la longueur des rectangles (des lignes et des colonnes) - ie comte de consécutives de 1 alors. Traverser les deux temp matrices de trouver max répéter longueurs (des lignes et des colonnes).

Voici le code pour le même.

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

OriginalL'auteur Shyam