Проблема
Учитывая 2D grid
состоит из 0s
(земля) и 1s
(вода). остров – это максимальная 4-направленно связанная группа из 0s
, а замкнутый остров – это остров полностью (все левые, верхние, правые, нижние ) в окружении 1s.
Возвращает количество закрытых островов.
Пример 1:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Output: 2 Explanation: Islands in gray are closed because they are completely surrounded by water (group of 1s).
Пример 2:
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] Output: 1
Пример 3:
Input: grid = [[1,1,1,1,1,1,1], [1,0,0,0,0,0,1], [1,0,1,1,1,0,1], [1,0,1,0,1,0,1], [1,0,1,1,1,0,1], [1,0,0,0,0,0,1], [1,1,1,1,1,1,1]] Output: 2
Ограничения:
1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1
Решение
class Solution: def closedIsland(self, grid: List[List[int]]) -> int: numOfClosedIslands = 0 for row in range(len(grid)): for col in range(len(grid[0])): if grid[row][col] is 0 and self.isClosedIsland(grid, row, col): numOfClosedIslands += 1 return numOfClosedIslands def isClosedIsland(self, grid, row, col): if 0 <= row < len(grid) and 0 <= col < len(grid[0]): if grid[row][col] is 1: return True grid[row][col] = 1 right = self.isClosedIsland(grid, row, col +1) bottom = self.isClosedIsland(grid, row + 1, col) left = self.isClosedIsland(grid, row, col - 1) top = self.isClosedIsland(grid, row - 1, col) return right and bottom and left and top return False
Производительность
Надеюсь, статья была полезной. Пожалуйста, подпишитесь, чтобы не пропустить следующие статьи, и не стесняйтесь обращаться ко мне, если у вас есть какие-либо вопросы или предложения.