Nombre minimum de jours pour déconnecter l'île

1568. Nombre minimum de jours pour déconnecter l'île

Difficulté : Difficile

Sujets : Tableau, recherche en profondeur d'abord, recherche en largeur d'abord, matrice, composant fortement connecté

Vous recevez une grille binaire m x n où 1 représente la terre et 0 représente l'eau. Une île est un groupe maximal de 1 connectés dans 4 directions (horizontalement ou verticalement).

Le réseau est dit connecté si nous avons exactement une île, sinon est dit déconnecté.

En une journée, nous sommes autorisés à transformer n'importe quelle cellule terrestre (1) en cellule d'eau (0).

Renvoyer le nombre minimum de jours pour déconnecter le réseau.

Exemple 1 :

• Entrée : grille = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
• Sortie : 2
• Explication : Il nous faut au moins 2 jours pour obtenir un réseau déconnecté. Remplacez la grille terrestre[1][1] et la grille[0][2] par de l'eau et obtenez 2 îles déconnectées.

Exemple 2 :

• Entrée : grille = [[1,1]]
• Sortie : 2
• Explication : Le réseau de pleine eau est également déconnecté ([[1,1]] -> [[0,0]]), 0 îles.

Contraintes :

• m == grille.longueur
• n == grille[i].longueur
• 1 <= m, n <= 30
• grille[i][j] vaut 0 ou 1.

Indice :

1. Renvoyer 0 si le réseau est déjà déconnecté.
2. Renvoyer 1 si vous changez un seul terrain en eau, déconnectez l'île.
3. Sinon, retournez 2.
4. Nous pouvons déconnecter le réseau dans un délai maximum de 2 jours.

Solution :

Nous devons considérer les étapes suivantes :

Étapes pour résoudre le problème :

1. Vérifier la connectivité initiale : Tout d'abord, vérifiez si le réseau est déjà déconnecté en déterminant s'il y a plus d'une île dans le réseau. S'il est déjà déconnecté, renvoyez 0.

2. Vérifiez si une seule suppression déconnecte l'île : parcourez chaque cellule de la grille. Convertissez temporairement la cellule de 1 à 0 (si c'est 1) et vérifiez si le réseau se déconnecte en comptant le nombre d'îlots. Si la conversion d'une seule cellule déconnecte l'îlot, renvoyez 1.

3. Déconnexion de deux jours : Si aucune conversion de cellule unique ne déconnecte l'île, le réseau peut être déconnecté en convertissant deux cellules terrestres adjacentes. Par conséquent, retournez 2.

Fonctions clés :

• DFS (Depth-First Search) pour trouver et compter les îles.
• isConnected pour vérifier si le réseau est connecté.

Implémentons cette solution en PHP : 1568. Nombre minimum de jours pour déconnecter l'île

  
  
  Explication:




La fonction minDays() gère la logique principale.

countIslands() compte le nombre d'îles présentes à l'aide de DFS.

dfs() est la fonction récursive pour explorer la grille et marquer les cellules terrestres visité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!