腐烂的橘子

题目分析

题目描述的是一个典型的 多源广度优先搜索（BFS） 问题。在一个 m × n 的网格中，腐烂的橘子会以 四个方向（上、下、左、右）向外扩散，每经过一分钟，相邻的新鲜橘子（值 1）就会变成腐烂的橘子（值 2）。我们的目标是求出所有新鲜橘子变成腐烂橘子的最短时间。如果有新鲜橘子无法被腐蚀，则返回 -1。

解题思路

1. 数据预处理：

   • 遍历整个 grid，记录所有腐烂橘子的位置，将其存入 队列 queue 中（用于 BFS）。
   • 统计新鲜橘子的数量 fresh_count，如果 fresh_count == 0，则立即返回 0。

2. BFS 传播腐烂：

   • 使用 队列 进行 BFS 遍历，每次处理当前层的所有腐烂橘子，并让其四个方向上的新鲜橘子腐烂。
   • 让腐烂的橘子入队，fresh_count 减少。
   • 记录传播所需的分钟数 minutes。

3. 判断是否有无法腐烂的橘子：

   • 如果 fresh_count > 0，说明仍然有新鲜橘子无法被腐蚀，返回 -1；
   • 否则返回 minutes。

复杂度分析

• 时间复杂度：O(m*n)，因为每个单元格最多被访问一次。
• 空间复杂度：O(m*n)，队列在最坏情况下可能存储所有橘子的位置。

代码实现

Python 实现

from collections import deque

class Solution:
    def orangesRotting(self, grid):
        n, m = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0

        # 遍历网格，初始化队列和新鲜橘子计数
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    queue.append((i, j, 0))  # (行, 列, 时间)
                elif grid[i][j] == 1:
                    fresh_count += 1

        # 如果没有新鲜橘子，返回 0
        if fresh_count == 0:
            return 0

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        minutes = 0

        # BFS 遍历
        while queue:
            x, y, minutes = queue.popleft()

            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                    grid[nx][ny] = 2  # 腐烂橘子
                    queue.append((nx, ny, minutes + 1))
                    fresh_count -= 1

        return -1 if fresh_count > 0 else minutes

# 读取输入
if __name__ == "__main__":
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]
    
    solution = Solution()
    print(solution.orangesRotting(grid))

Java 实现

import java.util.*;

public class Main {
    public class Solution {
        public int orangesRotting(int[][] grid) {
            int n = grid.length, m = grid[0].length;
            Queue<int[]> queue = new LinkedList<>();
            int freshCount = 0;

            // 初始化队列和新鲜橘子数量
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 2) {
                        queue.offer(new int[]{i, j, 0}); // (行, 列, 时间)
                    } else if (grid[i][j] == 1) {
                        freshCount++;
                    }
                }
            }

            // 如果没有新鲜橘子，直接返回 0
            if (freshCount == 0) {
                return 0;
            }

            int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            int minutes = 0;

            // BFS 遍历
            while (!queue.isEmpty()) {
                int[] current = queue.poll();
                int x = current[0], y = current[1];
                minutes = current[2];

                for (int[] dir : directions) {
                    int nx = x + dir[0], ny = y + dir[1];

                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;  // 变成腐烂橘子
                        queue.offer(new int[]{nx, ny, minutes + 1});
                        freshCount--;
                    }
                }
            }

            return freshCount > 0 ? -1 : minutes;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.orangesRotting(grid));
    }
}

C++ 实现

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        queue<tuple<int, int, int>> q;
        int freshCount = 0;

        // 遍历网格，初始化队列和新鲜橘子数量
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j, 0}); // (行, 列, 时间)
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }

        // 如果没有新鲜橘子，直接返回 0
        if (freshCount == 0) return 0;

        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;

        // BFS 遍历
        while (!q.empty()) {
            auto [x, y, time] = q.front();
            q.pop();
            minutes = time;

            for (auto [dx, dy] : directions) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    q.push({nx, ny, minutes + 1});
                    freshCount--;
                }
            }
        }

        return freshCount > 0 ? -1 : minutes;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    Solution solution;
    cout << solution.orangesRotting(grid) << endl;

    return 0;
}

题目内容

在给定的 $m × n$ 网格 $grid$ 中，每个单元格可以有以下三个值之一：

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

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

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

输入描述

• 第一行两个整数$n,m$。
• 接下来有$n$行，每行$m$列，表示网格，每行里的数字以空格分隔。

输出描述

一个整数，表示答案。

样例1

输入

3 3
2 1 1
1 1 0
0 1 1

输出

4

说明

样例2

输入

3 3
2 1 1
0 1 1
1 0 1

输出

-1

说明

左下角的橘子（第 $2$ 行， 第$0$列）永远不会腐烂，因为腐烂只会发生在 $4$ 个方向上

样例3

输入

1 2
0 2

输出

0

说明

因为$0$ 分钟时已经没有新鲜橘子了，所以答案就是 $0$

提示

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