Graph Exploration Target: 10s
Flood-fill DFS: mark visited by changing '1' to '0'. Each DFS call covers one island. Count DFS starts.
def numIslands(grid):
m, n = len(grid), len(grid[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] = '0' # mark visited
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return countType it from memory. Go.