Trouver la plus grande sous-matrice carrée de celles dans une matrice carrée donnée de 0 et de 1?

Question

Ce qui suit a été donnée comme une question d'entrevue:

Écrivez une fonction qui affiche la taille de la plus grande sous-matrice carrée composée uniquement de ceux dans une matrice carrée de uns et de zéros.

Exemple 1:

0 1 
0 0 

sortie: 1

Exemple 2:

0 0 0 
0 1 1 
0 1 1 

sortie: 2

Exemple 3:

1 1 1 
1 1 1 
1 1 1 

Sortie 3

J'espérais une solution efficace à ce problème si possible.

Answer 1

Utilisez Search puis Dynamic Programming.

Answer 2

Première idée de mise en œuvre: Lancer la recherche sur la ligne r = 1. Trouvez la plus longue séquence de uns dans cette rangée et assignez cette longueur à x. Essayez de trouver une matrice carrée de celles dont le côté = x commence à la rangée r. En cas de succès, max = x. Si ce n'est pas le cas, diminuez x et répétez cette étape si x> 1. Si rien n'est trouvé, max pourrait être 0 ou 1.

Augmenter r, et répéter.

Ensuite, améliorez votre algorithme (arrêtez si les lignes restantes sont inférieures au courant max, et ainsi de suite).

Answer 3

Voici implémentation O (n) en C# en utilisant la programmation dynamique. Fondamentalement, vous construisez une autre matrice de plus grande taille (y compris lui-même) pendant que vous lisez chaque cellule de la matrice.

public static int LargestSquareMatrixOfOne(int[,] original_mat) 
    { 
     int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)]; 
     AccumulatedMatrix[0, 0] = original_mat[0, 0]; 
     int biggestSize = 1; 
     for (int i = 0; i < original_mat.GetLength(0); i++) 
     { 
      for (int j = 0; j < original_mat.GetLength(1); j++) 
      { 
       if (i > 0 && j > 0) 
       { 
        if (original_mat[i, j] == 1) 
        { 
         AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1; 
         if (AccumulatedMatrix[i, j] > biggestSize) 
         { 
          biggestSize = AccumulatedMatrix[i, j]; 
         } 
        } 
        else 
        { 
         AccumulatedMatrix[i, j] = 0; 
        } 
       } 
       else if ((i > 0 && j == 0) || (j > 0 && i == 0)) 
       { 
        if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; } 
        else { AccumulatedMatrix[i, j] = 0; } 
       } 
      } 
     } 
     return biggestSize; 
    }