200. 岛屿数量
mid
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
1
2
3
4
5
6
7
| 输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
|
示例 2：
1
2
3
4
5
6
7
| 输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
|
DFS
我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。（或者用一个 visited 数组标记到达过的陆地）
最终岛屿的数量就是我们进行深度优先搜索的次数。
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
| // with visited
func numIslands(grid [][]byte) int {
rows, cols := len(grid), len(grid[0])
visited := make([][]bool, rows)
for i, _ := range visited {
visited[i] = make([]bool, cols)
}
var explore func(x, y int)
explore = func(x, y int) {
if x < 0 || x > rows-1 || y < 0 || y > cols-1 || grid[x][y] == '0' || visited[x][y] {
return
}
visited[x][y] = true
explore(x+1, y)
explore(x, y+1)
explore(x-1, y)
explore(x, y-1)
}
count := 0
for x := 0; x < rows; x++ {
for y := 0; y < cols; y++ {
if grid[x][y] == '0' || visited[x][y] == true {
continue
}
count++
explore(x, y)
}
}
return count
}
|
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
| // without visited
func numIslands(grid [][]byte) int {
rows, cols := len(grid), len(grid[0])
var explore func(x, y int)
explore = func(x, y int) {
if x < 0 || x > rows-1 || y < 0 || y > cols-1 || grid[x][y] == '0' {
return
}
grid[x][y] = '0'
explore(x+1, y)
explore(x, y+1)
explore(x-1, y)
explore(x, y-1)
}
count := 0
for x := 0; x < rows; x++ {
for y := 0; y < cols; y++ {
if grid[x][y] == '0' {
continue
}
count++
explore(x, y)
}
}
return count
}
|