Unterinseln zählen

1905. Unterinseln zählen

Schwierigkeit:Mittel

Themen: Array, Tiefensuche, Breitensuche, Unionssuche, Matrix

Sie erhalten zwei m x n-Binärmatrizen, Gitter1 und Gitter2, die nur Nullen (für Wasser) und Einsen (für Land) enthalten. Eine Insel ist eine Gruppe von Einsen, die in 4 Richtungen (horizontal oder vertikal) verbunden sind. Alle Zellen außerhalb des Gitters gelten als Wasserzellen.

Eine Insel in Raster2 wird als Unterinsel betrachtet, wenn es in Raster1 eine Insel gibt, die alle die Zellen enthält, aus denen diese Insel in Raster2 besteht .

Gibt die Anzahl der Inseln in Raster2 zurück, die als Unterinseln gelten.

Beispiel 1:

• Eingabe: Grid1 = [[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]], Gitter2 = [[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]]
• Ausgabe: 3
• Erklärung:
  • Im Bild oben ist das Gitter links Gitter1 und das Gitter rechts Gitter2.
  • Die in Raster 2 rot gefärbten Einsen gelten als Teil einer Unterinsel. Es gibt drei Unterinseln.

Beispiel 2:

• Eingabe: Grid1 = [[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]], Gitter2 = [[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]]
• Ausgabe: 2
• Erklärung:
  • Im Bild oben ist das Gitter links Gitter1 und das Gitter rechts Gitter2.
  • Die in Raster 2 rot gefärbten Einsen gelten als Teil einer Unterinsel. Es gibt zwei Unterinseln.

Einschränkungen:

• m == gitter1.länge == gitter2.länge
• n == Grid1[i].length == Grid2[i].length
• 1 <= m, n <= 500
• Grid1[i][j] und Grid2[i][j] sind entweder 0 oder 1.

Hinweis:

1. Lassen Sie uns Floodfill verwenden, um über die Inseln des zweiten Gitters zu iterieren
2. Beachten wir Folgendes: Wenn alle Zellen einer Insel im zweiten Gitter durch Land im ersten Gitter dargestellt werden, sind sie verbunden, wodurch diese Insel zu einer Unterinsel wird

Lösung:

Wir verwenden den DFS-Ansatz (Depth-First Search), um die Inseln in Raster2 zu erkunden und zu prüfen, ob jede Insel vollständig in einer entsprechenden Insel in Raster1 enthalten ist. So können wir die Lösung umsetzen:

Schritte:

1. Das Raster durchqueren:Wir durchlaufen jede Zelle in Raster2.
2. Inseln in Raster2 identifizieren:Wenn wir in Raster2 auf eine Landzelle (1) stoßen, verwenden wir DFS, um die gesamte Insel zu erkunden.
3. Unterinselbedingung prüfen: Während wir DFS auf einer Insel in Raster2 durchführen, prüfen wir, ob alle entsprechenden Zellen in Raster1 auch Landzellen sind. Wenn ja, handelt es sich bei der Insel um eine Unterinsel.
4. Unterinseln zählen: Für jede Insel in Raster 2, die die Unterinselbedingung erfüllt, erhöhen wir die Anzahl unserer Unterinseln.

Lassen Sie uns diese Lösung in PHP implementieren: 1905. Unterinseln zählen

  
  
  Erläuterung:




DFS-Funktion: Die DFS-Funktion erkundet die Insel in Raster2 und prüft, ob die entsprechenden Zellen in Raster1 alle Landzellen sind. Wenn eine Zelle in Gitter2 Land ist, die entsprechende Zelle in Gitter1 jedoch Wasser ist, ist die Insel in Gitter2 keine Unterinsel.

Besucht markieren: Während wir Grid2 durchqueren, markieren wir Zellen als besucht, indem wir sie auf 0 setzen.

Hauptschleife: Wir durchlaufen alle Zellen in Raster2. Immer wenn wir eine Landzelle finden, die noch nicht besucht wurde, initiieren wir ein DFS, um zu prüfen, ob sie Teil einer Unterinsel ist.



  
  
  Zeitkomplexität:


Die Zeitkomplexität beträgt (O(m mal n)), wobei m die Anzahl der Zeilen und n die Anzahl der Spalten ist. Dies liegt daran, dass wir möglicherweise jede Zelle einmal besuchen.

Diese Lösung sollte innerhalb der gegebenen Einschränkungen effizient funktionieren.

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 vonUnterinseln zählen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!