Алгоритми та структури даних · Middle · Запитання 30 з 75
Як порахувати острови (зв'язні групи одиниць) у сітці з 0 і 1?
- ✓Правильна відповідь: Запускати BFS чи DFS із кожної невідвіданої 1, позначаючи її острів
- 2Відсортувати кожен рядок і порахувати в ньому серії одиниць
- 3Порахувати всі одиниці й поділити суму на чотири
Пояснення
Кожен обхід позначає одну компоненту зв'язності, тож кількість запущених обходів і є відповіддю. Кожна клітинка відвідується сталу кількість разів: O(rows × cols).