-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0200 [M] Number of Islands
Code with Senpai edited this page Jul 19, 2021
·
15 revisions
same as number of connected components just with a built-in visited check and neighbor list with the grid the DFS in this case "sinks" the islands and marks them visited
if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != '1': return
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1': # keep going
DIRS = [(+1,0), (-1,0), (0,-1), (0,+1)]
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
n_rows, n_cols = len(grid), len(grid[0])
n_connected = 0
def dfs(r, c):
# here anything that's not '1' acts as not relevant or visited already
if 0 <= r < n_rows and 0 <= c < n_cols and grid[r][c] == '1': # inbounds and connected
grid[r][c] = 0 # sink/mark visited
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
dfs(nr, nc)
for r in range(n_rows):
for c in range(n_cols):
if grid[r][c] == '1':
n_connected += 1
dfs(r, c)
return n_connected
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(r, c):
# here anything that's not '1' acts as not relevant or visited already
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1':
grid[r][c] = 0 # sink/mark visited
dfs(r+1,c) ; dfs(r-1,c) ; dfs(r,c+1) ; dfs(r,c-1)
num_components = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
num_components += 1
dfs(r, c)
return num_components
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(r, c):
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1':
grid[r][c] = 'v'
list(map(dfs,
(r+1, r-1, r, r),
(c, c, c+1, c-1)
))
return 1
return 0
return sum(dfs(r, c) for r in range(len(grid)) for c in range(len(grid[0])))
footer