RU | EN | FR | JP | DE | CH | KR
Gegeben ist eine Seenkarte, die als zweidimensionales Array dargestellt ist, wobei jede Zelle entweder Wasser ('W') oder Land ('L') ist. Die Aufgabe besteht darin, die Anzahl einzelner Inseln auf dieser Karte zu bestimmen. Eine Insel wird definiert als eine Gruppe benachbarter (senkrecht oder waagerecht verbundener) Landzellen, die von Wasser umgeben sind.
Beispiel Seenkarte:
[ ['W', 'L', 'W', 'W'], ['W', 'L', 'L', 'W'], ['W', 'W', 'L', 'W'], ['L', 'W', 'W', 'L'] ]
Erwartetes Ergebnis: Auf der Karte gibt es 3 separate Inseln. Eine Insel besteht aus zwei benachbarten 'L'-Zellen in der zweiten Spalte, die zweite besteht aus einer Zelle in der dritten Zeile, dritte Spalte, und die dritte besteht aus zwei nicht diagonal benachbarten Zellen in der letzten Zeile.
- Entwickeln Sie einen Algorithmus mit Breitensuche (BFS), um die Anzahl der Inseln auf der Karte zu bestimmen.
- Visualisieren Sie den Suchprozess, indem Sie besuchte und überprüfte Zellen markieren.
- Zählen Sie die Anzahl der Schritte (Bewegungen) während des Suchprozesses.
- Initialisieren Sie einen Inselzähler und eine leere Warteschlange für BFS.
- Iterieren Sie durch jede Zelle auf der Karte.
- Wenn die aktuelle Zelle Land ist und noch nicht besucht wurde, starten Sie BFS, um nach einer Insel zu suchen.
- Während BFS markieren Sie besuchte Zellen und erhöhen Sie den Schrittzähler.
- BFS endet, wenn wir alle benachbarten Zellen der aktuellen Insel durchlaufen haben.
- Wiederholen Sie die Schritte 3-5 für alle Zellen auf der Karte.
Während der Ausführung des Algorithmus visualisieren wir besuchte und überprüfte Zellen. Dies hilft, den Prozess der Suche nach Inseln auf der Karte visuell darzustellen.
Nach Abschluss des Algorithmus erhalten wir die Anzahl der einzelnen Inseln auf der Seenkarte und die Anzahl der Schritte (Bewegungen) während des Suchprozesses.
Dieses Projekt steht unter der MIT-Lizenz - siehe die Datei LICENSE für Details.