Untitled

 avatar
unknown
python
a year ago
1.5 kB
5
Indexable
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # what defines an unclosed island? when a seq of 0's can reach the side of the grid
        # starting from each 0 if you can complete do dfs, if we can complete dfs without having a 0 connected to the edge, that is a closed island
        # within the dfs function, use a flag to keep track of if it hits the edge and only plus 1 to the result if the flag is false

        maxR = len(grid) - 1
        maxC = len(grid[0]) - 1

        def dfs(r, c):
            isClosed = 1
            stack = []
            stack.append((r, c))
            while stack:
                r, c = stack.pop()
                grid[r][c] = 1
                if r == 0 or r == maxR or c == 0 or c == maxC:
                    isClosed = False
                if r - 1 >= 0 and grid[r - 1][c] == 0:
                    stack.append((r - 1,c))
                if r + 1 <= maxR and grid[r + 1][c] == 0:
                    stack.append((r + 1, c))
                if c - 1 >= 0 and grid[r][c - 1] == 0:
                    stack.append((r, c - 1))
                if c + 1 <= maxC and grid[r][c + 1] == 0:
                    stack.append((r, c + 1))
            
            return isClosed
        
        res = 0
        for r in range(maxR + 1):
            for c in range(maxC + 1):
                if grid[r][c] == 0:
                    if dfs(r, c):
                        res += 1
        
        return res
Editor is loading...
Leave a Comment