200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

def numIslands(grid: List[List[str]]):

       

    visited = set()

    num_islands = 0

   

    m, n = len(grid), len(grid[0])

    dirs = [(-1,0), (1, 0), (0, -1), (0, 1)]

   

    for r in range(m):

        for c in range(n):

            if (r,c) not in visited and grid[r][c] == '1':

                num_islands += 1

               

                explore = [(r, c)]

                visited.add((r,c))                    

               

                while explore:

                    i,j = explore.pop()

                    visited.add((i,j))

                   

                    surrounding = [(i+di, j+dj) for di, dj in dirs]

                   

                    for si, sj in surrounding:

                        if si >=0 and si < m and sj >=0 and sj < n:

                            if (si,sj) not in visited and grid[si][sj] == '1':                            

                                explore.append((si,sj))

                   

    return num_islands