Проблема

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

Производительность

Надеюсь, статья была полезной. Пожалуйста, подпишитесь, чтобы не пропустить следующие статьи, и не стесняйтесь обращаться ко мне, если у вас есть какие-либо вопросы или предложения.

Твиттер | ЛинкедИн | "Поддержите меня"