Сложность: medium
Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.
Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой.
Пример:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
👨💻 Алгоритм:
1️⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS).
2️⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый.
3️⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.
😎 Решение:
class Solution:
def numIslands(self, grid):
if not grid:
return 0
num_islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
self.dfs(grid, i, j)
num_islands += 1
return num_islands
def dfs(self, grid, r, c):
if (
r < 0
or c < 0
or r >= len(grid)
or c >= len(grid[0])
or grid[r][c] != "1"
):
return
grid[r][c] = "0"
self.dfs(grid, r - 1, c)
self.dfs(grid, r + 1, c)
self.dfs(grid, r, c - 1)
self.dfs(grid, r, c + 1)
Ставь 👍 и забирай 📚 Базу знаний