本文目录
1 中文题目
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，可以假设该网格的四条边均被水包围。
示例：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.lengthn == grid[i].length- 1 ≤ m , n ≤ 300 1 \leq m, n \leq 300 1≤m,n≤300
grid[i][j]的值为 ‘0’ 或 ‘1’
2 Python求解
2.1 求解思路
通过遍历整个网格，每当发现一个未访问的陆地（‘1’）时，使用深度优先搜索将与其相连的所有陆地都标记为已访问（修改为’0’），同时计数器加1，这样每次DFS标记的就是一个完整的岛屿，最终计数器的值就是岛屿的数量。
2.2 涉及方法
- 深度优先搜索（Depth-First Search, DFS）
- 洪水填充算法（Flood Fill Algorithm）
2.3 求解示例
输入矩阵
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
第一次发现陆地：grid[0][0] = '1'
count = 1
执行DFS，标记第一个岛屿（标记为'0'）：
[["0","0","0","0","0"],
["0","0","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]
第二次发现陆地：grid[2][2] = '1'
count = 2
执行DFS，标记第二个岛屿：
[["0","0","0","0","0"],
["0","0","0","0","0"],
["0","0","0","0","0"],
["0","0","0","1","1"]]
第三次发现陆地：grid[3][3] = '1'
count = 3
执行DFS，标记第三个岛屿：
[["0","0","0","0","0"],
["0","0","0","0","0"],
["0","0","0","0","0"],
["0","0","0","0","0"]]
最终返回：3
2.4 Python代码
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 获取网格的行数和列数
rows = len(grid)
if not rows:
return 0
cols = len(grid[0])
# 岛屿计数器
count = 0
# 深度优先搜索函数，用于标记相连的陆地
def dfs(i: int, j: int) -> None:
# 边界检查和水域检查
if (i < 0 or i >= rows or
j < 0 or j >= cols or
grid[i][j] != '1'):
return
# 将当前陆地标记为已访问（修改为'0'）
grid[i][j] = '0'
# 递归访问上下左右四个方向
dfs(i-1, j) # 上
dfs(i+1, j) # 下
dfs(i, j-1) # 左
dfs(i, j+1) # 右
# 遍历整个网格
for i in range(rows):
for j in range(cols):
# 发现未访问的陆地
if grid[i][j] == '1':
count += 1 # 发现新岛屿
dfs(i, j) # 标记整个岛屿
return count
2.5 复杂度分析
- 时间复杂度：O(m×n)，m和n分别是网格的行数和列数
- 每个格子最多被访问一次
- DFS的递归调用不会重复访问已标记的格子
- 总体需要遍历整个网格一次
- 空间复杂度：O(m×n)
- 最坏情况下（整个网格都是陆地且呈蛇形）
- DFS的递归调用栈深度可能达到m×n
- 在实际情况下，递归深度通常远小于m×n
3 题目总结
题目难度：中等
数据结构：矩阵
应用算法：深度优先搜索（Depth-First Search, DFS）