Medium DFS Recursive Advanced Graphs
In plain English: Count separate groups of connected land cells in a grid.
Each unvisited '1' starts a new island. DFS/BFS from it marks all connected land as visited — the number of fresh DFS calls equals the number of islands.
Prompt
Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.
Try to write it from scratch before scrolling down.
Solution
def num_islands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 0
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '#' # mark visited
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
# Test: grid = [["1","1","0"],["1","0","0"],["0","0","1"]] => 2