LeetCode 200. 岛屿数量
题目描述
思路分析
感染问题
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func numIslands(grid [][]byte) int {
if len(grid) <= 0 || len(grid[0]) <= 0 {
return 0
}
var res int
m, n := len(grid), len(grid[0])
var dfs func(i, j int)
dfs = func(i, j int) {
// 边界条件，越界或遇到水
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0' {
return
}
// 将当前陆地标记为水，防止重复访问
grid[i][j] = '0'
dfs(i-1, j) // 上
dfs(i+1, j) // 下
dfs(i, j-1) // 左
dfs(i, j+1) // 右
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
res++
dfs(i, j)
}
}
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func numIslands(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
m, n := len(grid), len(grid[0])
count := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
count++
dfs(grid, i, j)
}
}
}
return count
}
func dfs(grid [][]byte, i, j int) {
if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] != '1' {
return
}
grid[i][j] = 2
dfs(grid, i-1, j)
dfs(grid, i+1, j)
dfs(grid, i, j-1)
dfs(grid, i, j+1)
}
时间复杂度：
O(m * n)，每个节点最多被访问一次。空间复杂度：
O(m * n)，递归调用栈的深度最坏情况下为网格的大小。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！