## [994\. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)

You are given an `m x n` `grid` where each cell can have one of three values:

- `0` representing an empty cell,
- `1` representing a fresh orange, or
- `2` representing a rotten orange.

Every minute, any fresh orange that is **4-directionally adjacent** to a rotten orange becomes rotten.

Return _the minimum number of minutes that must elapse until no cell has a fresh orange_. If _this is impossible, return_ `-1`.

**Example 1:**


**Input:** grid = \[\[2,1,1\],\[1,1,0\],\[0,1,1\]\]
**Output:** 4

**Example 2:**

**Input:** grid = \[\[2,1,1\],\[0,1,1\],\[1,0,1\]\]
**Output:** -1
**Explanation:** The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

**Example 3:**

**Input:** grid = \[\[0,2\]\]
**Output:** 0
**Explanation:** Since there are already no fresh oranges at minute 0, the answer is just 0.

**Constraints:**

- `m == grid.length`
- `n == grid[i].length`
- `1 <= m, n <= 10`
- `grid[i][j]` is `0`, `1`, or `2`.

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        
        // 用來存花了多少分鐘
        int minutes = 0;
        
        // 用來存剩下多少橘子
        int fresh = 0;
        queue<pair<int, int>> q;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                // 如果遇到 1，新鮮橘子 + 1
                if(grid[i][j] == 1) fresh++;
                // 如果遇到 2，壞橘子推到 queue
                else if(grid[i][j] == 2) q.push({i, j});
            }
        }

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

        while(!q.empty() && fresh > 0) {
            int qSize = q.size();
            for(int i = 0; i < qSize; i++) {
                auto node = q.front(); q.pop();
                for(auto& dir : directions) {
                    int new_r = node.first + dir[0];
                    int new_c = node.second + dir[1];
                    // 遇到超出邊界的、不是好橘子的都略過
                    if(new_r < 0 || new_c < 0 || new_r >= rows || new_c >= cols || grid[new_r][new_c] != 1)
                        continue;

                    // 標記新的格子已經是壞橘子
                    grid[new_r][new_c] = 2;
                    q.push({new_r, new_c});
                    fresh--;
                }
            }
            // queue 搜索完一輪，minutes++
            minutes++;
        }
        // 判斷最後還有新鮮橘子，return -1
        return fresh == 0 ? minutes : -1;
    }
};

:::success
- 時間複雜度：$O(M \cdot N)$
- 空間複雜度：$O(M \cdot N)$
:::