Untitled

mail@pastecode.io avatar
unknown
python
2 months ago
1.2 kB
3
Indexable
Never
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # traverse through grid, dfs through islands and check if neighbors valid, mark visited islands -1

        # init vars
        rows = len(grid)
        cols = len(grid[0])
        islands = 0
        dirs = [(0,1), (1,0), (0,-1), (-1,0)]
        
        def valid_coord(r, c):
            return 0 <= r < rows and 0 <= c < cols

        def dfs(r, c):
            stack = []
            stack.append((r, c))

            while stack:
                y, x = stack.pop()
                grid[y][x] = -1 # mark visited

                for dx, dy in dirs:
                    nr, nc = y + dy, x + dx

                    # an island is only not closed if surrounded by edges
                    if not valid_coord(nr, nc):
                        return False

                    if grid[nr][nc] == 0:
                        stack.append((nr, nc))
                
            return True

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    islands += 1 if dfs(r, c) else 0

        return islands
Leave a Comment