Algorithmen und Datenstrukturen · Middle · Frage 30 von 75
Wie zählt man Inseln (zusammenhängende Gruppen aus 1en) in einem Gitter aus 0en und 1en?
- 1Ab jeder unbesuchten 1 per BFS/DFS die Insel markieren
- 2Jede Zeile sortieren und darin die Folgen von 1en zählen
- 3Alle 1en zählen und die Summe durch vier teilen
Antwort zeigen
Richtige Antwort: Ab jeder unbesuchten 1 per BFS/DFS die Insel markieren
Erklärung
Jede Traversierung markiert eine Zusammenhangskomponente, die Zahl der gestarteten Traversierungen ist also die Antwort. Jede Zelle wird eine konstante Zahl von Malen besucht: O(rows × cols).