Mindestanzahl an Tagen zum Trennen der Insel

1568. Mindestanzahl an Tagen zum Trennen der Insel

Schwierigkeit:Schwer

Themen: Array, Tiefensuche, Breitensuche, Matrix, stark verbundene Komponente

Sie erhalten ein m x n-Binärgitter, wobei 1 für Land und 0 für Wasser steht. Eine Insel ist eine maximal in 4 Richtungen (horizontal oder vertikal) verbundene Gruppe von Einsen.

Das Netz gilt als verbunden, wenn wir genau eine Insel haben, ansonsten heißt es getrennt.

An einem Tag dürfen wir jede einzelne Landzelle (1) in eine Wasserzelle (0) verwandeln.

Geben Sie die Mindestanzahl an Tagen für die Trennung vom Netz zurück.

Beispiel 1:

• Eingabe: Gitter = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
• Ausgabe: 2
• Erklärung:Wir brauchen mindestens 2 Tage, um ein getrenntes Netz zu bekommen. Ändern Sie Landnetz[1][1] und Netz[0][2] in Wasser und erhalten Sie 2 getrennte Inseln.

Beispiel 2:

• Eingabe: Gitter = [[1,1]]
• Ausgabe: 2
• Erklärung:Gitter mit vollem Wasser ist ebenfalls getrennt ([[1,1]] -> [[0,0]]), 0 Inseln.

Einschränkungen:

• m == Gitterlänge
• n == grid[i].length
• 1 <= m, n <= 30
• Grid[i][j] ist entweder 0 oder 1.

Hinweis:

1. Gib 0 zurück, wenn das Netz bereits getrennt ist.
2. Gib 1 zurück, wenn ein einzelnes Land in Wasser umgewandelt wird, trenne die Insel.
3. Andernfalls geben Sie 2 zurück.
4. Wir können das Netz innerhalb von höchstens 2 Tagen trennen.

Lösung:

Wir müssen die folgenden Schritte berücksichtigen:

Schritte zur Lösung des Problems:

1. Überprüfen Sie die anfängliche Konnektivität: Überprüfen Sie zunächst, ob das Netz bereits getrennt ist, indem Sie feststellen, ob es mehr als eine Insel im Netz gibt. Wenn die Verbindung bereits getrennt ist, geben Sie 0 zurück.

2. Überprüfen Sie, ob die Insel durch einmaliges Entfernen getrennt wird: Durchlaufen Sie jede Zelle des Rasters. Wandeln Sie die Zelle vorübergehend von 1 auf 0 um (falls sie 1 ist) und prüfen Sie, ob das Netz unterbrochen wird, indem Sie die Anzahl der Inseln zählen. Wenn durch die Konvertierung einer einzelnen Zelle die Insel getrennt wird, geben Sie 1 zurück.

3. Zweitägige Trennung: Wenn keine einzelne Zellenumwandlung die Insel trennt, kann das Netz durch Umwandlung zweier benachbarter Landzellen getrennt werden. Geben Sie daher 2 zurück.

Schlüsselfunktionen:

• DFS (Depth-First Search)um Inseln zu finden und zu zählen.
• isConnected um zu prüfen, ob das Netz angeschlossen ist.

Lassen Sie uns diese Lösung in PHP implementieren: 1568. Mindestanzahl an Tagen zum Trennen der Insel

  
  
  Erläuterung:




Die Funktion minDays() verwaltet die Hauptlogik.

countIslands() zählt mit DFS, wie viele Inseln vorhanden sind.

dfs() ist die rekursive Funktion zum Erkunden des Gitters und zum Markieren besuchter Landzellen.


Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonMindestanzahl an Tagen zum Trennen der Insel. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!