947. La plupart des pierres supprimées avec la même ligne ou colonne
Difficulté :Moyen
Sujets :Table de hachage, recherche en profondeur d'abord, recherche d'union, graphique
Sur un plan 2D, nous plaçons n pierres à des points de coordonnées entiers. Chaque point de coordonnées peut avoir au plus une pierre.
Une pierre peut être supprimée si elle partage soitla même ligne ou la même colonnequ'une autre pierre qui n'a pas été supprimée.
Étant donné un tableau de pierres de longueur n où pierres[i] = [xi, yi] représente l'emplacement de la ièmepierre, renvoiele plus grand nombre possible de pierres pouvant être supprimées.
Exemple 1 :
Exemple 2 :
Exemple 3 :
Contraintes :
Solution :
Nous pouvons mettre en œuvre la solution en utilisant une approche Depth-First Search (DFS). L’idée est de considérer les pierres reliées par des lignes ou des colonnes comme faisant partie du même composant connecté. Une fois que vous avez trouvé tous les composants connectés, le nombre maximum de pierres pouvant être supprimées est le nombre total de pierres moins le nombre de composants connectés.
Implémentons cette solution en PHP :947. La plupart des pierres supprimées avec la même ligne ou colonne
Explication:
Fonction DFS:
- La fonction dfs est utilisée pour explorer toutes les pierres qui se trouvent dans le même composant connecté. Si une pierre est connectée (dans la même ligne ou colonne) à la pierre actuelle, nous effectuons récursivement DFS sur cette pierre.
Fonction principale:
- Nous parcourons toutes les pierres, et pour chaque pierre qui n'a pas été visitée, nous effectuons un DFS pour marquer toutes les pierres dans le même composant connecté.
- Nous comptons le nombre de composants connectés, et le résultat est le nombre total de pierres moins le nombre de composants connectés ($n - $numComponents).
Exemple d'exécution:
- Pour le premier exemple, il trouve correctement que 5 pierres peuvent être retirées, laissant 1 pierre qui ne peut pas être retirée.
Complexité:
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 auréférentielsur 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 :
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!