Учитывая mxn 2D-сетку двоичной сетки, которая представляет карту «1» (земля) и «0» (вода), верните количество островов.

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

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        if not grid: 
            return 0

        rows, cols = len(grid), len(grid[0])

        islands = 0
        visited = set()

        def bfs(r, c):
            q = collections.deque()
            visited.add((r, c))
            q.append((r, c))

            while q: 
                row, col = q.pop()
                directions = [
                    [1, 0], [-1, 0],
                    [0, 1], [0, -1]
                ]
                for dr, dc in directions: 
                    if(
                        (r + dr) in range(rows) 
                        and (c + dc) in range(cols)
                        and grid[r+dr][c+dc] == "1" 
                        and (r+dr, c+dc) not in visited

                    ):
                        visited.add((r+dr, c+dc))
                        q.append((r+dr, c+dc))
                        bfs(r+dr, c+dc)



        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    bfs(r, c)
                    islands += 1


        return islands 







Войти в полноэкранный режим

Выйти из полноэкранного режима