Код Senior Графы: BFS и DFS обновлено
Число островов
Условие
Матрица из 0 и 1. Сколько связных областей из единиц (соседство по 4 сторонам)? Вход мутировать можно.
Примеры
numIslands([[1, 1, 0], [0, 1, 0], [0, 0, 1]]) // 2
numIslands([[0, 0], [0, 0]]) // 0
numIslands([]) // 0
Как подойти
Классический DFS по матрице. Затопление вместо отдельного множества посещённых экономит память. Проверка границ одной строкой в начале функции - то, что отличает чистое решение от каши из if.
Подсказки: 2
- Найдя единицу, «затопи» весь её остров и увеличь счётчик.
- Проверку границ делай в начале рекурсии, а не перед каждым вызовом.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.