Medium

题目描述

给你一个 m x n 的网格，其中每个单元格可以有以下三个值之一：

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

每分钟，腐烂的橘子周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行，第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] 的值为 0、1 或 2

解题思路

这是一个经典的多源BFS问题。我们需要模拟腐烂过程，每一轮同时处理所有当前腐烂的橘子。

核心思路：

  1. 将所有初始腐烂的橘子位置加入队列，作为BFS的起点
  2. 统计新鲜橘子的总数
  3. 使用BFS逐层扩展，每一轮处理队列中所有橘子，让它们感染相邻的新鲜橘子
  4. 每处理完一轮，时间增加1分钟
  5. 当队列为空时，检查是否还有新鲜橘子剩余

算法步骤：

  • 遍历网格，收集所有腐烂橘子的坐标并入队，同时统计新鲜橘子数量
  • 进行BFS：每轮处理当前队列中的所有腐烂橘子，让它们感染四个方向的新鲜橘子
  • 新被感染的橘子加入队列，新鲜橘子计数减1
  • 重复直到队列为空
  • 如果最后还有新鲜橘子，返回-1；否则返回经过的时间

这种方法确保了同一时刻腐烂的橘子同时扩散，完美模拟了题目要求的腐烂过程。

代码实现

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        int fresh = 0;
        
        // 收集腐烂橘子位置，统计新鲜橘子数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        
        if (fresh == 0) return 0;
        
        int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;
        
        while (!q.empty()) {
            int size = q.size();
            bool hasNewRotten = false;
            
            for (int i = 0; i < size; i++) {
                auto [x, y] = q.front();
                q.pop();
                
                for (auto& dir : directions) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        q.push({nx, ny});
                        fresh--;
                        hasNewRotten = true;
                    }
                }
            }
            
            if (hasNewRotten) minutes++;
        }
        
        return fresh == 0 ? minutes : -1;
    }
};

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque()
        fresh = 0
        
        # 收集腐烂橘子位置，统计新鲜橘子数量
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1
        
        if fresh == 0:
            return 0
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        minutes = 0
        
        while queue:
            size = len(queue)
            has_new_rotten = False
            
            for _ in range(size):
                x, y = queue.popleft()
                
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                        grid[nx][ny] = 2
                        queue.append((nx, ny))
                        fresh -= 1
                        has_new_rotten = True
            
            if has_new_rotten:
                minutes += 1
        
        return minutes if fresh == 0 else -1

public class Solution {
    public int OrangesRotting(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        Queue<(int, int)> queue = new Queue<(int, int)>();
        int fresh = 0;
        
        // 收集腐烂橘子位置，统计新鲜橘子数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.Enqueue((i, j));
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        
        if (fresh == 0) return 0;
        
        int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            bool hasNewRotten = false;
            
            for (int i = 0; i < size; i++) {
                var (x, y) = queue.Dequeue();
                
                for (int d = 0; d < 4; d++) {
                    int nx = x + directions[d, 0];
                    int ny = y + directions[d, 1];
                    
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        queue.Enqueue((nx, ny));
                        fresh--;
                        hasNewRotten = true;
                    }
                }
            }
            
            if (hasNewRotten) minutes++;
        }
        
        return fresh == 0 ? minutes : -1;
    }
}

var orangesRotting = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const queue = [];
    let freshCount = 0;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 2) {
                queue.push([i, j]);
            } else if (grid[i][j] === 1) {
                freshCount++;
            }
        }
    }
    
    if (freshCount === 0) return 0;
    
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    let minutes = 0;
    
    while (queue.length > 0) {
        const size = queue.length;
        let hasRotten = false;
        
        for (let i = 0; i < size; i++) {
            const [row, col] = queue.shift();
            
            for (const [dr, dc] of directions) {
                const newRow = row + dr;
                const newCol = col + dc;
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] === 1) {
                    grid[newRow][newCol] = 2;
                    queue.push([newRow, newCol]);
                    freshCount--;
                    hasRotten = true;
                }
            }
        }
        
        if (hasRotten) minutes++;
    }
    
    return freshCount === 0 ? minutes : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)每个单元格最多被访问一次
空间复杂度O(m×n)最坏情况下队列存储所有单元格

相关题目