LeetCode Hot 100 P994 Rotting Oranges

---

timeline

timeline

2026-03-15

init

BFS

---

Problem:

P994 Rotting Oranges

https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked

BFS is sufficient. Note the case where all are empty cells; in that case, return 0 directly.

#include <vector>
#include <queue>
#include <utility>

using std::queue;
using std::vector;
using std::pair;

class Solution {
    public:
        int orangesRotting(vector<vector<int> > &grid)
        {
                int i, j, k, m = grid.size(), n = grid[0].size();
                int minutes = 0;
                int nr_rot;

                queue<pair<int, int> > que;
                vector<vector<bool> > pushed(m, vector<bool>(n, false));

                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (grid[i][j] == 0 || grid[i][j] == 1)
                                        continue;
                                que.push({ i, j });
                                pushed[i][j] = true;
                        }
                }

                while (!que.empty()) {
                        nr_rot = que.size();
                        for (k = 0; k < nr_rot; k++) {
                                auto [i, j] = que.front();
                                grid[i][j] = 2;
                                que.pop();

                                // Up
                                if (i - 1 >= 0 && !pushed[i - 1][j] && grid[i - 1][j] == 1) {
                                        que.push({ i - 1, j });
                                        pushed[i - 1][j] = true;
                                }

                                // below
                                if (i + 1 < m && !pushed[i + 1][j] && grid[i + 1][j] == 1) {
                                        que.push({ i + 1, j });
                                        pushed[i + 1][j] = true;
                                }

                                // Left

                                if (j - 1 >= 0 && !pushed[i][j - 1] && grid[i][j - 1] == 1) {
                                        que.push({ i, j - 1 });
                                        pushed[i][j - 1] = true;
                                }

                                // Right
                                if (j + 1 < n && !pushed[i][j + 1] && grid[i][j + 1] == 1) {
                                        que.push({ i, j + 1 });
                                        pushed[i][j + 1] = true;
                                }
                        }

                        minutes++;
                }

                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (grid[i][j] == 1)
                                        return -1;
                        }
                }

                return (minutes == 0) ? 0 : (minutes - 1);
        }
};