LeetCode 994. 腐烂的橘子

Categories:

题目描述
思路分析
1. 解法一：多源 BFS（推荐）
相似题目

题目描述

✅ 994. 腐烂的橘子

思路分析

解法一：多源 BFS（推荐）

核心思路：

将所有腐烂橘子入队作为 BFS 起点。

每轮扩散到相邻新鲜橘子，时间加一。

统计新鲜橘子数量，最终若仍有未腐烂则返回 -1。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 为网格行列数。

空间复杂度：O(mn)，队列最多存储一层节点。

// 多源 BFS 扩散腐烂
class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        int fresh = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }

        int minutes = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty() && fresh > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] d : dirs) {
                    int x = cur[0] + d[0];
                    int y = cur[1] + d[1];
                    if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1) {
                        continue;
                    }
                    grid[x][y] = 2;
                    fresh--;
                    queue.offer(new int[]{x, y});
                }
            }
            minutes++;
        }

        return fresh == 0 ? minutes : -1;
    }
}

// 多源 BFS 扩散腐烂
func orangesRotting(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	queue := make([][2]int, 0)
	fresh := 0

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

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

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

相似题目

题目	难度	考察点
200. 岛屿数量	中等	BFS/DFS
542. 01 矩阵	中等	多源 BFS
752. 打开转盘锁	中等	BFS
1091. 二进制矩阵中的最短路径	中等	BFS
1162. 地图分析	中等	多源 BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/72302154