Programmation dynamique - plus grand bloc carré

voici un croquis de la solution:

pour chacune des cellules nous allons garder un compteur de la taille d'un carré peut être fait en utilisant cette cellule en haut à gauche. Il est clair que toutes les cellules avec 0 auront 0 comme nombre.

commencer à itérer à partir de la cellule inférieure droite et aller en bas à gauche, puis passer à une rangée et répéter.

à chaque scan faites ceci:

1. si la case a 0, attribuer count=0
2. si la cellule a 1 et est une cellule de bord (bord inférieur ou droit seulement), attribuer count=1
3. pour toutes les autres cellules, vérifier le nombre de cellules à sa droite, en bas à droite et en bas. Prenez le min d'entre eux et ajoutez 1 et assignez cela au compte. Gardez une variable globale max_count pour garder la trace du nombre max jusqu'à présent.

À la fin de la traversée de la matrice, max_count aura la valeur souhaitée.

complexité n'est plus que le coût de traversée de la matrice.

C'est comme ça que la matrice ressemblera après la traversée. Les valeurs entre parenthèses sont les nombres, c'est-à-dire le plus grand carré qui peut être fait en utilisant la cellule en haut à gauche.

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

implémentation en Python

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)

LSBRA(X,Y) signifie "Grand Carré avec Fond-Droit À X,Y"

Pseudo:

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

(pour les cellules de bord, vous pouvez sauter la partie MIN et juste retourner 1 si (x,y) n'est pas 0.)

Travail en diagonale à travers la grille en "vagues", comme suit:

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

ou alternativement, travaillez de gauche à droite, de haut en bas, aussi longtemps que vous remplissez les cellules de bord.

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

de cette façon, vous ne serez jamais exécuter dans un calcul où vous n'avez pas calculé auparavant les données nécessaires - de sorte que tous les LSBRA() " appels " sont en fait juste des tables de recherche de vos résultats de calcul précédents (d'où l'aspect de programmation dynamique).

pourquoi ça marche

pour avoir un carré avec un bas à droite à X, Y-il doit contenir les carrés de chevauchement d'une dimension de moins qui touchent chacun des autres 3 Coins. En d'autres termes, d'avoir

XXXX
XXXX
XXXX
XXXX

Vous devez aussi avoir

...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

aussi longtemps que vous avez ces 3 carrés (chacun des contrôles LSBRA) de taille N plus le carré actuel est aussi" occupé", vous aurez un carré de taille (N+1).

Le premier algorithme qui me vient à l'esprit est:

1. '&&' colonne/ligne 1 colonne/ligne 2 si, c'est-à-dire faire une "& & ' opération entre chaque entrée et son entrée correspondante dans l'autre colonne/rangée.
2. cochez la colonne résultante, s'il y a une longueur de 2 1 qui signifie que nous frappons un carré de 2x2.
3. Et la colonne suivante avec le résultat des deux premières. S'il y a n'importe quelle longueur 31's nous avons frappé un 3x3 carré.
4. répéter jusqu'à ce que toutes les colonnes aient été utilisées.
5. répéter 1-4 en commençant par la colonne 2.

Je ne vais pas vous montrer la mise en œuvre comme tout à fait simple et votre problème ressemble à des devoirs. De plus, il y a probablement des moyens beaucoup plus efficaces de le faire, car cela deviendra lent si les entrées étaient très importantes.

la matrice D'entrée Let est M : n x m

T[i][j] est une matrice DP qui contient le plus grand côté carré avec un angle inférieur droit (i,j) .

règle Générale pour remplir le tableau:

if (M[i][j] == 1) {
  int v = min(T[i][j-1], T[i-1][j]);
  v = min(v, T[i-1][j-1]);
  T[i][j] = v + 1;
}
else 
  T[i][j] = 0;

la taille carrée du résultat est la valeur max dans T .

remplissage T[i][0] et T[0][j] est sans importance.

Je ne suis pas sûr que cet algo puisse être utilisé pour votre énorme fichier , mais vous n'avez pas besoin de stocker la matrice entière T mais seulement les lignes actuelles et précédentes seulement.

les notes suivantes peuvent aider à undestand idée générale:

• tous les carrés avec les angles inférieurs droits (i-1, j), (i, j-1), (i-1, j-1) avec la taille s sont à l'intérieur du carré avec l'angle inférieur droit (i, j) avec la taille s+1.
• s'il y a un carré de taille s+1 avec coin inférieur droit à (i, j), puis la taille du carré maximal avec angle inférieur droit (i-1, j), (i, j-1), (i-1, j-1) est au moins S.
• ci-contre est également vrai. Si la taille d'au moins un carré avec des angles droits inférieurs à (i-1, j), (i, j-1), (i-1, j-1) est inférieure à s, alors la taille du carré avec le coin inférieur droit à (i, j) ne peut pas être plus grande que s+1.

OK, la manière la plus inefficace mais simple serait:

1. sélectionner le premier élément. vérifiez si 1, si vous avez un carré de 1x1.

2. cochez une case ci-dessous et une case à droite, si 1, puis cochez la ligne 2 col 2, Si 1, 2x2 carré.

3. cochez la rangée 3 col 1, col 2 et col 3, plus la rangée 1 col 3, la rangée 2 col 3, Si 1, 3x3.

4. So en gros, vous continuez à étendre la rangée et col ensemble et vérifier toutes les cellules à l'intérieur de leurs limites. Dès que vous frappez un 0, Il est cassé, donc vous vous déplacez le long d'un point dans une rangée, et recommencer.

5. au bout de la rangée, passez à la rangée suivante.

6. jusqu'à la fin.

vous pouvez probablement voir comment ceux-ci s'insèrent tandis que les boucles, etc, et comment && s peut être utilisé pour vérifiez le 0s, et en le regardant, vous remarquerez peut-être aussi comment il peut être accéléré. Mais comme l'autre réponse vient de le mentionner, cela ressemble un peu à des devoirs donc nous allons laisser le code réel à vous.

bonne chance!

la clé ici est que vous pouvez garder la trace de la racine de la zone au lieu de la zone réelle, en utilisant la programmation dynamique.

L'algorithme est le suivant:

stocke un tableau 2D d'entrées appelé max-square, où un élément à l'index i,j représente la taille du carré dans lequel il est avec i,j étant le coin inférieur droit. (si max[i,j] = 2, cela signifie que l'indice i,j est le coin en bas à droite d'un carré de taille 2^2 = 4)

pour chaque indice i, j:

si au i,j l'élément est 0, puis définissez max-carré i,j à 0.

else:

"151900920 Trouver" le minimum de max-carré[i - 1, j] et max-carré[i, j - 1] et max-carré[i - 1][j -1]. réglez max-square[i, j] à 1 + Le minimum des 3. Inductivement, vous finirez par remplir le tableau de max-square. Rechercher/ou de garder une trace de la valeur maximale dans le processus, retourner cette valeur^2.

regardez ces solutions que les gens ont proposées: https://leetcode.com/discuss/questions/oj/maximal-square?sort=votes

soit N la quantité de cellules dans le tableau 2D. Il existe un algorithme très efficace pour lister tous les rectangles vides maximums. Le plus grand carré vide est à l'intérieur d'un de ces rectangles vides, et la fondation est triviale une fois que la liste des rectangles vides maximum a été calculée. Un article présentant un algorithme O(N) pour créer une telle liste peut être trouvé à www.ulg.ac.be/telecom/rectangles ainsi que le code source (non optimisé). Notez qu'une preuve existe (voir le papier) que le nombre de plus grands rectangles vides est limité par N. Par conséquent, le choix du plus grand carré vide peut être fait dans O(N), et la méthode globale est également O (N). En pratique, cette méthode est très rapide. L'implémentation est très facile à faire, puisque le code entier ne doit pas dépasser 40 lignes de C (l'algorithme pour lister tous les rectangles vides prend environ 30 lignes de C).