Leetcode 994. Rotting Oranges

medium

class Solution {
    int maxR{0};
    int maxC{0};
    int time{0};
    queue<pair<int, int>> rottenQ; // rotten orange locations
    
public:
    void visit(vector<vector<int>>& grid, int r, int c) {
        // visit only next depth
        int next[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        for (int i=0; i<4; i++) {
            int R = r+next[i][0];
            int C = c+next[i][1];
            if (R>=maxR || C>=maxC || R<0 || C<0 || grid[R][C]==0 || grid[R][C]==2) {
                continue;
            }
            rottenQ.push(make_pair(R,C));
            grid[R][C] = 2;
        }
    }
    
    int orangesRotting(vector<vector<int>>& grid) {
        maxR = grid.size();
        maxC = grid[0].size();
        
        // find all rotten oranges
        for (int r=0; r<maxR; r++) {
            for (int c=0; c<maxC; c++) {
                if (grid[r][c] == 2) {
                    rottenQ.push(make_pair(r,c));
                }
            }
        }
        
        // put a delimeter to specify there is no more rotten orange
        rottenQ.push(make_pair(-1, -1));
        
        // run breadth first search algorith to find depth
        pair<int, int> prev{0, 0};
        pair<int, int> curr{0, 0};
        while(!rottenQ.empty()) {
            prev = curr;
            curr = rottenQ.front();
            rottenQ.pop();
            if (curr.first == -1 && curr.second == -1) {
                if(prev.first == -1 && prev.second == -1) {
                    // two consecutive delimeter means there is no more rotten tomatoes
                    break;
                }
                // put a delimeter to identify all current depth's rotten tomatoes are handled
                rottenQ.push(make_pair(-1, -1));
                // increase the timer and pickup a new rotten tomato from rottenQ
                time++;
                continue;
            }
            
            // visit surrouding grid
            visit(grid, curr.first, curr.second);
        }
        
        // see if there is any fresh orange left
        for (int r=0; r<maxR; r++) {
            for (int c=0; c<maxC; c++) {
                if (grid[r][c] == 1) {
                    return -1; // it was impossible to rotten all oranges
                }
            }
        }  
        
        return time - 1;
    }
};

In case of

• [[2,1,1]
• ,[1,1,0]
• ,[0,1,2]]

rottenQ will be {2', 2', (-1,-1),2', 2', 2', (-1,-1), 2', 2', (-1,-1), (-1,-1)} where 2' means the location of a rotten tomato.