华为 OD 训练营 · 题解精讲
LeetCode200、岛屿数量
LeetCode200、岛屿数量 视频地址：https://ntpkq.xetlk.com/s/e4ZwM
题目描述
给你一个由 '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
题目解析
解题思路
本题要求统计二维网格中岛屿（由相邻陆地组成的连通块）的数量。核心思路是遍历整个网格，每当遇到一个未被访问的陆地，就将其视为一个新岛屿的起点，然后通过搜索算法标记该岛屿的所有陆地，避免重复计数。
参考代码提供了 DFS 和 BFS 两种实现，逻辑完全一致：使用一个 checkList 二维布尔数组记录每个格子是否已被访问。遍历网格时，若遇到陆地且未访问，则计数加一，并以此点为起点进行深度优先或广度优先搜索，将整个连通块的所有陆地标记为已访问。
关键步骤
1. 初始化：获取网格尺寸 x（行数）和 y（列数），创建与网格同大小的 checkList，初始值均为 False（未访问）。 2. 遍历网格：双重循环遍历每个格子。 3. 发现新岛屿：若 grid[i][j] == "1" 且 checkList[i][j] == False，则 ans += 1，并启动搜索。 4. 搜索过程（以 DFS 为例）：
- 将当前格子标记为已访问：
checkList[i][j] = True - 遍历四个方向（上、下、左、右），计算相邻坐标
(next_i, next_j) - 若相邻坐标未越界、未访问且为陆地，则递归调用 DFS
示意图（DFS 搜索顺序）：
初始：grid[0][0]为陆地，未访问
标记[0][0] → 向右搜索[0][1] → 标记 → 继续向右...
当遇到水或边界时回溯，再尝试其他方向复杂度分析
- 时间复杂度：O(m × n)，其中 m、n 分别为网格的行数和列数。每个格子最多被访问一次。
- 空间复杂度：O(m × n)。
checkList数组占用 O(m×n) 空间；DFS 递归栈深度在最坏情况下（整个网格为陆地）为 O(m×n)；BFS 的队列在最坏情况下也需 O(m×n) 空间。
参考代码
DFS解法
# 题目：LC200. 岛屿数量
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问
# 初始化上下左右四个方向的数组
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
class Solution:
# 构建DFS函数
def DFS(self, grid, i, j, checkList):
# 将该点标记为已经检查过
checkList[i][j] = True
# 遍历上下左右四个方向的邻点坐标
for dx, dy in DIRECTIONS:
next_i, next_j = i + dx, j + dy
# 若近邻点满足三个条件：
# 1.没有越界 2. 近邻点尚未被检查过 3.近邻点也为陆地
if ((0 <= next_i < self.x and 0 <= next_j < self.y) and checkList[next_i][next_j] == False
and grid[next_i][next_j] == "1"):
# 对近邻点(ni, nj)进行DFS搜索
self.DFS(grid, next_i, next_j, checkList)
def numIslands(self, grid: List[List[str]]) -> int:
self.x = len(grid) # 获得网格长
self.y = len(grid[0]) # 获得网格宽
ans = 0 # 初始化答案为0
# 初始化数组checkList用于DFS遍历过程中的检查
# 0表示尚未访问，1表示已经访问
checkList = [[False] * self.y for _ in range(self.x)]
# 对整个grid二维数组进行双重循环遍历
for i in range(self.x):
for j in range(self.y):
# 若该点为陆地且还没有进行过搜寻
if grid[i][j] == "1" and checkList[i][j] == False:
# 可以进行DFS
self.DFS(grid, i, j, checkList)
# 做完DFS，连通块数量+1，更新答案
ans += 1
return ans
BFS解法
# 题目：LC200. 岛屿数量
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问
# 初始化上下左右四个方向的数组
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
x_len, y_len = len(grid), len(grid[0]) # 获得网格长宽
ans = 0 # 初始化陆地数目为0
# 初始化和grid一样大小的二维数组checkList用于DFS遍历过程中的检查
checkList = [[0] * y_len for _ in range(x_len)]
# 双重遍历grid数组
for i in range(x_len):
for j in range(y_len):
# 若该点为陆地且还没有进行过搜寻
# 找到了一个BFS搜索的起始位置(i,j)
if grid[i][j] == "1" and checkList[i][j] == 0:
# 对于该片连通块，构建一个队列，初始化包含该点
q = deque()
q.append((i,j))
# 修改checkList[i][j]为1，表示该点已经搜寻过
checkList[i][j] = 1
# 进行BFS，退出循环的条件是队列为空
while len(q) > 0:
# 弹出栈队头的点(x,y) 搜寻该点上下左右的近邻点
x, y = q.popleft()
# 遍历(x,y)上下左右的四个方向的近邻点
for dx, dy in DIRECTIONS:
x_next, y_next = x+dx, y+dy
# 如果近邻点满足三个条件
if (0 <= x_next < x_len and 0 <= y_next < y_len and checkList[x_next][y_next] == 0
and grid[x_next][y_next] == "1"):
# 对近邻点做两件事：
# 1. 入队 2. 标记为已检查过
q.append((x_next, y_next))
checkList[x_next][y_next] = 1
# 连通块的数量+1
ans += 1
return ans