Дано: Задан двумерный двоичный массив m x n, представляющий собой карту из «1» (земля) и «0» (вода), нужно найти количество островов на карте.
Примечание: Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Предполагаются, что все четыре края карты окружены водой.
Пример 1:
Вход:
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Выход: 1
Пример 2:
Вход:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Выход: 3
Ограничения:
m == длина матрицы
n == grid[i].length - высота матрицы
1 <= m, n <= 300
значение grid[i][j] равно '0' или '1'.
Решение:
Для решения данной проблемы нужно разделить задачу на 2 части:
1)Как последовательно пройти все водные блоки( нули) один за другим.
Для этого мы просто циклом в цикле построчно проходим все клеточки в матрице.
2) Как обойти всю сушу(соседние земли (единицы) по горизонтали или вертикали), как только вы найдете первый сухопутный блок (единицу).
Мы представляем все острова суши (соединенные единицы) как графы, если мы натыкаемся на один из «сухопутных» узлов (единицу), мы приостанавливаем обход цикла по нулям, и начинаем обход графа, останавливаемся только тогда, когда граф полностью пройден, дальше возвращаемся в цикл обхода нулей.
Существует 2 основных алгоритма, из которых мы можем выбирать. Depth First Search (DFS) и Breath First Search (BFS).
Ответ: оба варианта одинаково быстры. Существуют ситуации, в которых DFS лучше BFS или наоборот. Но в данном случае это не имеет значения.
План состоит в том, чтобы двигаться от индекса к индексу и искать землю.
Как только мы найдем землю, мы начинаем использовать DFS или BFS для ее обхода (потому что оба метода одинаково быстры).
Как только мы обошли весь граф/остров, мы возвращаемся к поиску земли с той точки, на которой остановились. И перед тем как снова начать поиск земли, мы увеличиваем количество островов на единицу.
Разберём обход острова более подробно:
каждый "земельный блок" или "1" - это узел на графе. И мы можем как бы перемещаться от узла к узлу, если между ними есть земля (связь) , то есть узлы соединены вершинами.
Для перемещения используем вышеупомянутый DFS или BFS.
Разбор кода, применим обход в глубину (DFS):
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows = len(grid)
cols = len(grid[0])
totalIslands = 0
for i in range(rows):
for j in range(cols):
if int(grid[i][j]) == 1:
totalIslands += 1
self.visit_is_land_DFS(grid, i, j)
return totalIslands
def visit_is_land_DFS(self, grid, x, y):
if (x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0])):
return
if (int(grid[x][y]) == 0):
return
grid[x][y] = 0
self.visit_is_land_DFS(grid, x + 1, y)
self.visit_is_land_DFS(grid, x - 1, y)
self.visit_is_land_DFS(grid, x, y + 1)
self.visit_is_land_DFS(grid, x, y - 1)
sol = Solution()
print(sol.numIslands([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]))
Задаём переменную для подсчёта островов (totalIslands) и переменные для размера матрицы (rows и cols)
Проходим циклом матрицу, если натыкаемся на остров (grid[i][j] == 1) увеличиваем количество найденных островов и запускаем метод visit_is_land_DFS (обход графа в длину):
if (x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0])): - проверяем, что наши индексы ещё находятся внутри матрицы.
if (grid[x][y] == 0): - проверяем, что это часть острова, а не вода.
grid[x][y] = 0 - когда мы прошли часть острова, теперь она становится водой, чтобы при дальнейшем проходе цикла, снова не попасть на этот остров.
дальше запускаем рекурсию метода по вертикали и горизонтали пока не получим все нули вокруг острова или не выйдем за пределы матрицы.
Временная сложность: O(n * m), где n– количество строк, m– количество столбцов. - то есть наш цикл в цикле.
Пространственная сложность: O(m * n). В худшем случае, когда вся сетка заполнена землями, стек вызовов вырастет до количества ячеек в сетке.
Большинство информации украдено отсюда: https://livefiredev.com/number-of-islands-leetcode-explained-with-animations-visualizations/.