Graph DFS
200. Number of Islands
Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
We can use dfs to solve this problem:
- for all nodes in matrix:
- If not visited, dfs
- set it as visited
- go through 4 directions, if the (x, y) are valid, do dfs()
- count += 1
- If not visited, dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
self.dirs = [[0,1], [1,0],[-1,0], [0,-1]]
res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] != '0':
self.dfs(grid, i, j)
res += 1
return res
def dfs(self, grid: List[List[str]], row: int, col: int):
grid[row][col] = '0'
for direction in self.dirs:
x = row + direction[0]
y = col + direction[1]
if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == '1':
self.dfs(grid, x, y)
305. Number of Islands II
Union-find
