Описание

Учитывая 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.

Надеюсь, это было вам полезно. Спасибо за прочтение! Жду ваших отзывов. До скорой встречи ✌️