题目描述：
给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。一个岛屿被水包围，并且通过水平方向或垂直方向上相邻的陆地连接形成。你可以假设网格的四个边都被水包围。
示例：
输入:
11110
11010
11000
00000
输出: 1
输入:
11000
11000
00100
00011
输出: 3
解题思路：
这个问题可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。基本思路是遍历整个网格，每当遇到一个 '1' 时，就从这个位置开始进行深度优先搜索或广度优先搜索，将所有与其相连的 '1' 都标记为 '0'，这样可以避免重复计数。每进行一次这样的搜索，岛屿数量就增加 1。
深度优先搜索（DFS）解法：
- 遍历网格的每一个单元格。
- 当遇到一个
'1'时，从这个位置开始进行深度优先搜索，将所有与其相连的'1'都标记为'0'。 - 每次启动新的深度优先搜索时，岛屿数量增加 1。
代码实现（Python）：
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
def dfs(i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
return
grid[i][j] = '0' # 标记为已访问
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count广度优先搜索（BFS）解法：
- 遍历网格的每一个单元格。
- 当遇到一个
'1'时，从这个位置开始进行广度优先搜索，将所有与其相连的'1'都标记为'0'。 - 每次启动新的广度优先搜索时，岛屿数量增加 1。
代码实现（Python）：
from collections import deque
class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0
def bfs(i, j):
queue = deque([(i, j)])
while queue:
x, y = queue.popleft()
if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == '1':
grid[x][y] = '0' # 标记为已访问
queue.append((x + 1, y))
queue.append((x - 1, y))
queue.append((x, y + 1))
queue.append((x, y - 1))
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
bfs(i, j)
count += 1
return count复杂度分析：
- 时间复杂度： O(M * N)，其中 M 和 N 分别是网格的行数和列数。每个单元格最多被访问一次。
- 空间复杂度： O(M N)，在最坏情况下，如果整个网格都是陆地，递归调用栈的深度或队列的大小可以达到 M N。
这两种方法都可以有效地解决这道题目，选择其中一种即可。希望这些详细的解释和代码示例对你有所帮助！
发表回复