Untitled
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