往期博客：

Leetcode1-两数之和详解

Leetcode2-两数相加代码详解

Leetcode20-有效的括号详解

Leetcode21-合并两个有序链表详解

Leetcode22-有效括号生成详解

Leetcode24-两两交换链表中的节点详解

Leetcode27-移除元素详解

Leetcode46-全排列详解

Leetcode49-字母异位分组详解

Leetcode53-最大子数组和详解

Leetcode56-合并区间详解

LeetCode57-插入区间详解

Leetcode77-组合详解

Leetcode78-子集详解

Leetcode90-子集II详解

Leetcode94-二叉树的中序遍历详解

Leetcode102-二叉树的层序遍历详解

Leetcode107-二叉树的层序遍历II详解

Leetcode169-多数元素详解

---

目录

题目

示例

解析

DFS

BFS

代码

DFS

BFS

---

题目

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

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

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

分析：

1. 数字1的部分为大陆，数字0的部分为岛屿

2. 大陆只能与上下左右的1组成，斜对角方向的1不能组成

---

示例

示例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

---

解析

DFS

对于示例2，首先根据规则可以看到，总共有三个岛屿

使用DFS方法的思想进行分析，首先第一步可以设置一个指针，指针初始指向（0,0）的位置，由于只能上下左右的1能构成岛屿，所以第二步将（0,0）位置上下左右的1变成0，证明这些1已经与（0,0）位置构成了岛屿，然后第三步再将指针指向（0,1）位置移动，第四步同样将上下左右的1变成0，然后再移动，直到当前位置的上下左右全部为0没有1时，说明当前岛屿已经结束，再继续移动找下一个岛屿，直到到达整个二维数组的最后。

根据示例2详细分析

 当指针继续移动到（0,2）的位置时，此位置的上下左右全部为0，说明没有符合的1能继续组成岛屿，所以此时岛屿1已经全部找到。

继续移动指针，去找下一个岛屿......

当指针移动到（2，2）的位置时，出现了1，说明又有新的岛屿出现了，同样进行1变0的操作，但是此时上下左右都是0，说明岛屿已经全部找到，这是一个“小岛屿”

同样继续移动指针，去找下一个岛屿......

当指针移动到（3,3）的位置时又出现了1，说明有新的岛屿出现，将上下左右的1变为0

当指针移动到最后时，所有区域都已经遍历完了

BFS

BFS方法的过程也是找上下左右的1的过程，不过这里要用到队列，大致过程为第一步将指针指向（0,0）的位置，第二步将该位置的坐标放入队列中，第三步从队列中取出坐标位置，第四步将坐标上下左右为1的位置放入队列中

 第五步将上下左右为1的位置变为0，第六步取出队列第一个元素，并将其上下左右为1的位置放入队列，第七步将为1的位置变成0

 依次取出队列中的坐标，并判断上下左右是否有1，直到队列中没有坐标

移动指针，直到移动到下一个为1 的位置，则找到第二个岛屿

 移动指针，找到第三个岛屿

---

代码

DFS

class Solution: def numIslands(self, grid: List[List[str]]) -> int: if grid is None or len(grid) == 0: # 如果整个区域为空，则无岛屿，直接返回0 return 0 result = 0 # 记录岛屿数量 row = len(grid) # 整个区域的行数 col = len(grid[0]) # 整个区域的列数 # 用2个for循环遍历整个区域 for i in range(0, row): for j in range(0, col): if grid[i][j] == '1': # 找到了新岛屿 result += 1 self.dfs(grid, i, j, row, col) return result def dfs(self, grid, x, y, row, col): # (x,y)为当前指针所指位置 # x,y在区域外时直接停止循环 if x<0 or y<0 or x>=row or y>= col or grid[x][y]=='0': return grid[x][y] = '0' #将1变0 # 找上下左右为1的位置变0 self.dfs(grid, x-1, y, row, col) # 左边变0 self.dfs(grid, x+1, y, row, col) # 右边变0 self.dfs(grid, x, y-1, row, col) # 上边变0 self.dfs(grid, x, y+1, row, col) # 下边变0

BFS

class Solution: def numIslands(self, grid: List[List[str]]) -> int: if grid is None or len(grid) == 0: # 如果整个区域为空，则无岛屿，直接返回0 return 0 result = 0 # 记录岛屿数量 row = len(grid) # 整个区域的行数 col = len(grid[0]) # 整个区域的列数 queue = [] for i in range(0, row): for j in range(0, col): if grid[i][j] == '1': result += 1 queue.append([i,j]) grid[i][j] = '0' while len(queue) > 0: cur = queue.pop() x = cur[0] y = cur[1] if x-1 >= 0 and grid[x-1][y] == '1': queue.append([x-1,y]) grid[x-1][y] = '0' if y-1 >= 0 and grid[x][y-1] == '1': queue.append([x,y-1]) grid[x][y-1] = '0' if x+1