Проблема

Учитывая m x n 2D-бинарную сетку grid, которая представляет собой карту '1's (суша) и '0's (вода), вернуть количество островов.

Остров окружен водой и образован путем соединения соседних земель по горизонтали или вертикали. Вы можете предположить, что все четыре края сетки окружены водой.

Пример 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Пример 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Ограничения:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

Решение

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        numOfIslands = 0
        
        for r in range(len(grid)):
            for c in range(len(grid[r])):
                numOfIslands += self.getNeighbors(grid, r, c)

        return numOfIslands

    def getNeighbors(self, grid, r, c):
        if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] is not '0':
            grid[r][c] = '0'

            self.getNeighbors(grid, r, c + 1)
            self.getNeighbors(grid, r + 1, c)
            self.getNeighbors(grid, r, c - 1)
            self.getNeighbors(grid, r - 1, c)

            return 1

        return 0

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

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

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