Задача: 200. Number of Islands Сложность: 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) Ставь 👍 и забирай 📚 Базу знаний