Algorytmy i struktury danych · Middle · Pytanie 30 z 75
Jak policzyć wyspy (spójne grupy jedynek) w siatce zer i jedynek?
- ✓Poprawna odpowiedź: Uruchamiać BFS lub DFS z każdej nieodwiedzonej 1, oznaczając jej wyspę
- 2Posortować każdy wiersz i policzyć w nim serie jedynek
- 3Policzyć wszystkie jedynki i podzielić sumę przez cztery
Wyjaśnienie
Każde przejście oznacza jedną spójną składową, więc liczba uruchomionych przejść jest odpowiedzią. Każda komórka jest odwiedzana stałą liczbę razy: O(rows × cols).