200.岛屿数量

dfs, bfs, https://leetcode.cn/problems/number-of-islands/

给你一个由 '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.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

计算二维网格中的岛屿数量，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）。以下是基于 DFS 的解决方案：

python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            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)  # 右

        # 初始化岛屿计数器
        num_islands = 0
        
        # 遍历整个网格
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':  # 找到新的岛屿
                    num_islands += 1
                    dfs(i, j)  # 使用 DFS 标记整个岛屿
        
        return num_islands

200.岛屿数量 ​

200.岛屿数量