难度: Medium
给你一个由 '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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 的值为 '0' 或 '1'运行时间: 200 ms
内存: 0.0 MB
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
count += 1
self.dfs(grid, i, j)
return count
def dfs(self, grid, i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '#'
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)
这个题解使用深度优先搜索（DFS）的方法来解决岛屿数量问题。首先遍历整个网格，当遇到一个值为 '1' 的网格时，就将岛屿数量加一，然后以该网格为起点进行 DFS 搜索。在 DFS 搜索中，首先将当前网格标记为 '#' 表示已访问过，然后递归地对上下左右四个方向进行搜索。通过 DFS 搜索，可以将一个岛屿的所有陆地网格都标记为已访问，这样就不会重复计数。最终岛屿的数量即为进行 DFS 搜索的次数。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
count += 1
self.dfs(grid, i, j)
return count
def dfs(self, grid, i, j):
# 判断当前位置是否越界或不是陆地
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
return
# 将当前位置标记为已访问
grid[i][j] = '#'
# 递归搜索上下左右四个方向
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)
在 DFS 搜索中，将 '1' 修改为 '#' 是为了标记已访问的网格，避免重复访问和计数，从而减少不必要的递归调用。选择 '#' 或其他非 '1' 的字符都可以达到相同的效果，主要是为了区分未访问的 '1' 和已访问的状态。这种标记方法直接修改了原数组，节省了额外的空间开销，提升了空间效率，但要注意这种修改是破坏性的，原始数据将不被保留。
是的，在最坏情况下（例如一个大型网格完全由 '1' 组成），递归深度可以达到 m*n，这可能导致栈溢出。为避免此问题，可以使用非递归的方式实现 DFS，即利用一个显式的栈来模拟递归过程。另外，也可以采用广度优先搜索（BFS）使用队列来处理，这样每次扩展都是一层一层的，不会有深度递归所带来的栈溢出风险。
题解中已经包含了对边界情况的处理。在 `dfs` 函数的开始，有一个判断条件检查当前坐标是否越界（即索引是否小于0或大于等于网格的长度或宽度），以及当前位置是否为 '1'。如果不满足这些条件，函数将直接返回，不会继续执行。这样的处理确保了算法只在网格的有效区域内操作，防止了数组越界的错误。
如果网格中有大片的 '0' 区域，DFS 方法在遍历到 '0' 的格子时不会进行递归调用，因此这部分区域的处理是快速的。然而，DFS 仍然需要遍历每个格子至少一次以确认其状态。对于大型稀疏网格，一个更优的策略可能是使用并查集（Union-Find）数据结构。并查集可以更有效地处理大量分散的 '1' 网格，尤其是在处理多次查询和联合操作时，可以更快地进行群组的合并和查询操作。