腐烂的橘子

GitHub跳转原题关系图返回列表

所有腐烂橘子同时入队，多源 BFS 按层传播，统计分钟。

OJ: leetcodecn

题目 ID: rotting-oranges

难度:普及+/提高

标签:BFS多源网格cpppython

日期: 2026-07-29 13:10

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

每分钟腐烂橘子会使相邻新鲜橘子腐烂，求全部腐烂所需最少分钟。

思路

多源 BFS：所有初始腐烂橘子入队，按层传播。每层表示一分钟，统计新鲜橘子数。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size(), fresh = 0, mins = 0;
        queue<pair<int, int>> q;
        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++;
            }
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!q.empty() && fresh) {
            mins++;
            for (int sz = q.size(); sz--; q.pop()) {
                auto [x, y] = q.front();
                for (auto [dx, dy] : dirs) {
                    int nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        fresh--;
                        q.push({nx, ny});
                    }
                }
            }
        }
        return fresh ? -1 : mins;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    vector<vector<int>> g(m, vector<int>(n));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];
    cout << Solution().orangesRotting(g) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
from collections import deque
from typing import List


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque()
        fresh = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1
        mins = 0
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while q and fresh:
            mins += 1
            for _ in range(len(q)):
                x, y = q.popleft()
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                        grid[nx][ny] = 2
                        fresh -= 1
                        q.append((nx, ny))
        return -1 if fresh else mins


def main():
    m, n = map(int, input().split())
    g = [list(map(int, input().split())) for _ in range(m)]
    print(Solution().orangesRotting(g))


if __name__ == "__main__":
    main()

复杂度

时间 O(mn)，空间 O(mn)。

总结

多源 BFS 适合同时从多个起点开始扩散的问题。