Untitled
unknown
python
a year ago
1.2 kB
7
Indexable
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
Editor is loading...
Leave a Comment