994. 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;
    }
};

• T: $O(M \cdot N)$
• S: $O(M \cdot N)$