刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/number-of-islands/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个由 '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编码上会简单些，不过希望BFS也别忘了

DFS

• 找一个起点，首先判断当前点是否在边界内
• 然后分别找上下左右四个点，递归之

BFS

• 同样先找一个起点，先判断当前点是否在边界内
• 分别取相邻四个点，看是否符合条件，符合再以这一批新的起点继续遍历

其次是防止重复遍历

你可能会想到存一个二维数组啥的，但是这个题里没有必要，因为遍历过的点我们也不会再走，根据题意后续其实也没什么作用了，我们大可以直接改变下点的值，就像喷射战士刷漆那样！！这样也方便我们防止重复统计岛屿数量。

最后是防止重复统计岛屿数量

这里就很简单了，在我们以之前的起点进行搜索并标记（记录）之后，我们新的起点满足题目条件 + 没有被走过，那这个时候，就是一个新的岛屿了，数量加一即可！

代码

func numIslands(grid [][]byte) int {
	m := len(grid)
	n := len(grid[0])
	var dfs func(grid [][]byte, r, c int)
	dfs = func(grid [][]byte, i, j int) {
		if i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == '1' {
			grid[i][j] = '0'
			dfs(grid, i+1, j)
			dfs(grid, i-1, j)
			dfs(grid, i, j+1)
			dfs(grid, i, j-1)
		}
	}

	num := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				num++
				dfs(grid, i, j)
			}
		}
	}
	return num
}