Compter les sous-îles

1905. Compter les sous-îles

Difficulté :Moyen

Sujets : Tableau, recherche en profondeur d'abord, recherche en largeur d'abord, recherche d'union, matrice

Vous recevez deux matrices binaires m x n Grid1 et Grid2 contenant uniquement des 0 (représentant l'eau) et des 1 (représentant la terre). Une île est un groupe de 1 connectés dans 4 directions (horizontalement ou verticalement). Toutes les cellules en dehors de la grille sont considérées comme des cellules d'eau.

Une île dans la grille2 est considérée comme une sous-île s'il y a une île dans la grille1 qui contient toutes les cellules qui composent cette île dans la grille2 .

Renvoyer le nombre d'îles de la grille2 qui sont considérées comme des sous-îles.

Exemple 1 :

• Entrée : grille1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1, 0,0,0,0],[1,1,0,1,1]], grille2 = [[1,1,1,0,0],[0,0,1,1,1],[ 0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
• Sortie : 3
• Explication :
  • Dans l'image ci-dessus, la grille de gauche est la grille1 et la grille de droite est la grille2.
  • Les 1 colorés en rouge dans la grille2 sont ceux considérés comme faisant partie d'une sous-île. Il y a trois sous-îles.

Exemple 2 :

• Entrée : grille1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1, 1,1,1,1],[1,0,1,0,1]], grille2 = [[0,0,0,0,0],[1,1,1,1,1],[ 0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
• Sortie : 2
• Explication :
  • Dans l'image ci-dessus, la grille de gauche est la grille1 et la grille de droite est la grille2.
  • Les 1 colorés en rouge dans la grille2 sont ceux considérés comme faisant partie d'une sous-île. Il y a deux sous-îles.

Contraintes :

• m == grille1.longueur == grille2.longueur
• n == grille1[i].length == grille2[i].longueur
• 1 <= m, n <= 500
• grille1[i][j] et grille2[i][j] valent 0 ou 1.

Indice :

1. Utilisons Floodfill pour parcourir les îles de la deuxième grille
2. Notez que si toutes les cellules d'une île dans la deuxième grille si elles sont représentées par des terres dans la première grille alors elles sont connectées faisant ainsi de cette île une sous-île

Solution :

Nous utiliserons l'approche Depth-First Search (DFS) pour explorer les îles de la grille 2 et vérifier si chaque île est entièrement contenue dans une île correspondante dans la grille 1. Voici comment nous pouvons mettre en œuvre la solution :

Mesures:

1. Parcourir la grille : Nous allons parcourir chaque cellule de la grille2.
2. Identifier les îles dans la grille2 : Lorsque nous rencontrons une cellule terrestre (1) dans la grille2, nous utiliserons DFS pour explorer toute l'île.
3. Vérifier l'état de la sous-île : Lors de l'exécution de DFS sur une île de la grille2, nous vérifierons si toutes les cellules correspondantes de la grille1 sont également des cellules terrestres. Si c'est le cas, l'île est une sous-île.
4. Compte des sous-îles : Pour chaque île de la grille 2 qui répond à la condition de sous-île, nous incrémenterons notre nombre de sous-îles.

Implémentons cette solution en PHP : 1905. Compter les sous-îles

  
  
  Explication:




Fonction DFS : La fonction dfs explore l'île dans la grille2 et vérifie si les cellules correspondantes dans la grille1 sont toutes des cellules terrestres. Si une cellule de la grille 2 est une terre mais que la cellule correspondante de la grille 1 est de l'eau, l'île de la grille 2 n'est pas une sous-île.

Marquer les visites : Lorsque nous parcourons la grille 2, nous marquons les cellules comme visitées en les définissant sur 0.

Boucle principale : Nous parcourons toutes les cellules de la grille2. Chaque fois que nous trouvons une cellule terrestre qui n'a pas été visitée, nous lançons un DFS pour vérifier si elle fait partie d'une sous-île.



  
  
  Complexité temporelle :


La complexité temporelle est (O(m fois n)) où m est le nombre de lignes et n est le nombre de colonnes. En effet, nous visitons potentiellement chaque cellule une fois.

Cette solution devrait fonctionner efficacement dans les limites données.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!