C#, chercher et trouver la plus grande sous-matrice carrée composee uniquement de uns ('1') dans une table donnée. Implementer methode public static int FindLargestSquare(int[,] matrix) qui retourne la taille de la plus grande sous matrice carrée uniquement de uns dans la table à 2 dimensions matrix. contraintes: matrix est une table carrée, 0<= taille de matrix <= 100
public class Solution
{
public static int FindLargestSquare(int[,] matrix)
{
// Vérification si la matrice est vide ou a une taille 0
if (matrix == null || matrix.GetLength(0) == 0 || matrix.GetLength(1) == 0)
{
return 0;
}
int n = matrix.GetLength(0); // Taille de la matrice carrée
int[,] dp = new int[n, n]; // Tableau pour stocker les tailles des carrés
int maxSide = 0; // Variable pour garder la taille du plus grand carré trouvé
// Remplir la table dp
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i, j] == 1)
{
if (i == 0 || j == 0)
{
// Si on est dans la première ligne ou la première colonne
dp[i, j] = 1; // Le plus grand carré à cet endroit est de taille 1
}
else
{
// Utiliser la relation de récurrence pour les autres cellules
dp[i, j] = Math.Min(Math.Min(dp[i - 1, j], dp[i, j - 1]), dp[i - 1, j - 1]) + 1;
}
// Mettre à jour la taille maximale du carré
maxSide = Math.Max(maxSide, dp[i, j]);
}
else
{
dp[i, j] = 0; // Si la cellule est un 0, la taille du carré est 0
}
}
}
// La taille de la plus grande sous-matrice carrée est le carré de maxSide
return maxSide;
}
}
Aucun commentaire:
Enregistrer un commentaire