Описание
Учитывая m x n
2d grid
карту '1'
s (суша) и '0'
s (вода), верните количество островов.
Остров окружен водой и образован путем соединения соседних земель по горизонтали или вертикали. Вы можете предположить, что все четыре края сетки окружены водой.
Пример 1:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
Пример 2:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
Ограничения:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
is'0'
or'1'
.
Решение
Давайте посмотрим на Пример 1.
Как видим, это похоже на график. Но в отличие от графов, у которых есть дочерние элементы, здесь у нас есть соседи сверху-справа-снизу-слева. Итак, мы можем сказать, что нам нужно найти все компоненты связности в этом графе. В теории графов компонент неориентированного графа - это индуцированный подграф, в котором любые две вершины соединены друг с другом путями и который не связан ни с какими дополнительными вершинами в остальной части графа.
В примере 1 у нас есть только один связный компонент.
Пример 2 - три.
В этой задаче есть два крайних случая:
- Четыре края
grid
окружены водой (нам нужно проверить, вне сетки ли мы) - Мы должны посетить каждый
1
только один раз (избегайте бесконечной рекурсии)
Мы можем решить эту проблему, используя алгоритмы Поиск в ширину или Поиск в глубину. Начнем с DFS.
Давайте рассмотрим этот 2D-массив, и если мы увидим 1
, мы вызовемdfs
и увеличим некоторые острова counter
. И мы должны помнить о наших крайних случаях. Первый можно решить, проверив, находимся ли мы внутри drid
:
if ( i >= 0 && j >= 0 && i < grid.length && j < grid[i].length && grid[i][j] === '1' ) {...}
А второе можно решить, изменив каждую посещенную ячейку на 0
. Давайте посмотрим на все решение:
Временная сложность этого решения составляет O(nm)
, поскольку мы посещаем каждый элемент в 2D-массиве один раз. Пространственная сложность этого решения также равна O(nm)
в случае, если вся сетка заполнена 1
.
Теперь давайте разберемся, как решить эту проблему с помощью BFS.
Мы можем пройтись по всем ячейкам и делать то же самое - вызывать алгоритм bfs
каждый раз, когда мы видим 1
, и увеличивать некоторое counter
.
Пространственная и временная сложность этого решения такая же, как у алгоритма DFS
.
Надеюсь, это было вам полезно. Спасибо за прочтение! Жду ваших отзывов. До скорой встречи ✌️