200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'

很标准的dfs
可以省略 visited 标记数组，改为直接修改 grid 中已遍历的元素为 0， 1 之外的任意值即可

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
func numIslands(grid [][]byte) int {
	visited := make([][]bool, len(grid))
	for i := range visited {
		visited[i] = make([]bool, len(grid[0]))
	}
	ans := 0
	  
	var dfs func(int, int)
	dfs = func(m, n int) {
	// 到达边界
		if m >= len(grid) || n >= len(grid[0]) || m<0 || n<0 {
			return
		}
		// 到达岛边界
		if grid[m][n] == '0' {
			return
		}
		// 已访问的陆地跳过
		if visited[m][n] {
			return
		}
		// 标记陆地访问
		if grid[m][n] == '1' {
			visited[m][n] = true
		}
		  
		dfs(m-1, n)
		dfs(m+1, n)
		dfs(m, n+1)
		dfs(m, n-1)
	}
	  
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[0]); j++ {
			if !visited[i][j] && grid[i][j] == '1' {
				ans += 1
				dfs(i, j)
			}
		}
	}
	  
	return ans
}