🌊 BFS/DFS 实战：岛屿数量 & 腐烂的橘子（LeetCode 200 & 994）

两道图论基础题，涉及 BFS 与 DFS 的应用，主要用于掌握二维网格中遍历与标记访问的技巧：

• 🏝️ 200. 岛屿数量（Number of Islands）
• 🍊 994. 腐烂的橘子（Rotting Oranges）

🏝️ 一、200. 岛屿数量

📌 题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。

岛屿总是由相邻的陆地连接组成（水平或垂直），并且被水包围。

💡 解题思路

这道题的核心是：对每一个未被访问的陆地进行一次 DFS 或 BFS，将整块陆地标记为已访问，岛屿数量 +1。

✅ 方法一：DFS 深度优先遍历

• 从每个为 '1' 的位置出发，递归淹没它相邻的陆地；
• 每次新的 DFS 开始，即发现了一个新的岛屿。

func numIslands(grid [][]byte) int {
   
    m, n := len(grid), len(grid[0])
    var dfs func(int, int)
    dfs = func(i, j int) {
   
        if i < 0 || j < 0 || i >= m || j >= n || 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 := 0; i < m; i++ {
   
        for j := 0; j < n; j++ {
   
            if grid[i][j] == '1' {
   
                dfs(i, j)
                count++
            }
        }
    }
    return count
}

✅ 方法二：BFS 广度优先遍历

• 使用队列，每次将 '1' 入队后，通过四个方向将邻接陆地逐个加入队列。

🧠 小结

🍊 二、994. 腐烂的橘子

📌 题目描述

在一个二维网格中：

• 0 代表空单元格，
• 1 代表新鲜橘子，
• 2 代表腐烂橘子。

每分钟，所有腐烂橘子会让上下左右相邻的新鲜橘子变腐烂。
求腐烂完所有橘子的最短分钟数，如果无法全部腐烂，返回 -1。

💡 解题思路

这是标准的多源 BFS 问题，初始队列中包含所有腐烂橘子的位置，然后每轮向周围传播。

✅ 步骤总结：

1. 初始化队列，将所有腐烂橘子的坐标加入；
2. 记录新鲜橘子的数量 fresh；
3. 每轮扩散一层（即一分钟），对新鲜橘子变腐烂，fresh--；
4. 最终看 fresh 是否为 0，若是返回分钟数，否则返回 -1。

📦 Go 实现

type pair struct{
    x, y int }

func orangesRotting(grid [][]int) int {
   
    m, n := len(grid), len(grid[0])
    queue := []pair{
   }
    fresh := 0

    for i := 0; i < m; i++ {
   
        for j := 0; j < n; j++ {
   
            if grid[i][j] == 2 {
   
                queue = append(queue, pair{
   i, j})
            } else if grid[i][j] == 1 {
   
                fresh++
            }
        }
    }

    dirs := []pair{
   {
   0, 1}, {
   1, 0}, {
   0, -1}, {
   -1, 0}}
    minutes := 0

    for len(queue) > 0 && fresh > 0 {
   
        size := len(queue)
        for i := 0; i < size; i++ {
   
            curr := queue[0]
            queue = queue[1:]
            for _, d := range dirs {
   
                x, y := curr.x + d.x, curr.y + d.y
                if x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == 1 {
   
                    grid[x][y] = 2
                    fresh--
                    queue = append(queue, pair{
   x, y})
                }
            }
        }
        minutes++
    }

    if fresh > 0 {
   
        return -1
    }
    return minutes
}

⚠️ 注意事项

• 初始化时要统计新鲜橘子的数量；
• 每一轮是批量扩散（多源 BFS）；
• 不能单独计数某个腐烂橘子的时间，要整体一起推进。

🔚 总结对比