200. 岛屿数量 - 力扣（Leetcode）
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
func numIslands(grid [][]byte) int {
res := 0
r := len(grid)
c := len(grid[0])
visited := make([][]byte, r)
for i := 0; i < r; i++ {
visited[i] = make([]byte, c)
}
for i := 0; i < r; i++ {
for j := 0; j < c; j++ {
if grid[i][j] == '1' {
dfs(grid, i, j, visited)
res++
}
}
}
return res
}
func dfs(grid [][]byte, i int, j int, visited [][]byte) {
r := len(grid)
c := len(grid[0])
if i < 0 || j < 0 || i >= r || j >= c {
return
}
if grid[i][j] == '0' {
return
}
if visited[i][j] == '1' {
return
}
grid[i][j] = '0'
visited[i][j] = '1'
dfs(grid, i+1, j, visited)
dfs(grid, i, j+1, visited)
dfs(grid, i-1, j, visited)
dfs(grid, i, j-1, visited)
}
|
也可以使用方向二维数组来遍历
可以使用二维切片dirs表示方向变化值，将每个递归调用拆分为多个方向，并在循环中使用方向切片来更新i和j的值。示例如下：
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
| func dfs(grid [][]byte, i int, j int, visited [][]byte) {
r := len(grid)
c := len(grid[0])
dirs := [][]int{{1,0}, {-1,0}, {0,1}, {0,-1}}
if i < 0 || j < 0 || i >= r || j >= c {
return
}
if grid[i][j] == '0' {
return
}
if visited[i][j] == '1' {
return
}
grid[i][j] = '0'
visited[i][j] = '1'
for _, d := range dirs {
new_i, new_j := i + d[0], j + d[1]
dfs(grid, new_i, new_j, visited)
}
}
|
在上述示例代码中，我们定义了二维切片dirs，它保存了四个元素，分别代表四个方向的横向(x方向)和纵向(y方向)跨度。在dfs函数内部，我们遍历了dirs，并使用d[0]和d[1]来更新当前的i和j值。这样就可以对每个方向进行递归了。
使用额外的visited 的时候，一定要作为dfs 的入参，让其拷贝一份
在 dfs 函数的递归调用中，条件判断 if _, ok := visited[point{myRow, myCol}]; !ok 可能会导致部分陆地未被正确访问。原因是 visited 在函数调用之间是全局共享的，而不是每次调用都重新初始化（leetcode 的测试环境会造成影响）。
为了解决这个问题，你可以将 visited 变量作为参数传递给 dfs 函数，确保在每次调用时都使用新的局部副本。以下是修改后的代码：
需要注意的是，如上所述，使用dirs表示方向变化会稍微增加代码的复杂性，但它还可以使函数更灵活，并在处理其他需要迭代解决问题时提供帮助。
对应BFS实现
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| type point struct {
x int
y int
}
var dirct = [][]int{{1, 0}, {0, 1}, {0, -1}, {-1, 0}}
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
res := 0
r := len(grid)
c := len(grid[0])
for i := 0; i < r; i++ {
for j := 0; j < c; j++ {
if grid[i][j] == '1' {
res++
bfs(grid, i, j)
}
}
}
return res
}
func bfs(grid [][]byte, i, j int) {
r := len(grid)
c := len(grid[0])
queue := []point{{i, j}}
grid[i][j] = '0'
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
for _, item := range dirct {
myRow := current.x + item[0]
myCol := current.y + item[1]
if myRow >= 0 && myRow < r && myCol >= 0 && myCol < c && grid[myRow][myCol] == '1' {
grid[myRow][myCol] = '0'
queue = append(queue, point{myRow, myCol})
}
}
}
}
type point struct {
x int
y int
}
var dirct = [][]int{{1, 0}, {0, 1}, {0, -1}, {-1, 0}}
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
res := 0
r := len(grid)
c := len(grid[0])
visited := make(map[point]int)
for i := 0; i < r; i++ {
for j := 0; j < c; j++ {
if grid[i][j] == '1' {
res++
dfs(grid, i, j, visited)
}
}
}
return res
}
func dfs(grid [][]byte, i, j int, visited map[point]int) {
r := len(grid)
c := len(grid[0])
if i < 0 || j < 0 || i >= r || j >= c {
return
}
if grid[i][j] == '0' {
return
}
if _, ok := visited[point{i, j}]; ok {
return
}
grid[i][j] = '0'
visited[point{i, j}] = 1
for _, item := range dirct {
myRow := i + item[0]
myCol := j + item[1]
if _, ok := visited[point{myRow, myCol}]; !ok {
dfs(grid, myRow, myCol, visited)
}
}
}
|
https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/ 岛屿问题一文搞定
