Time Cost

31min10s

Code

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<int>> current(rows, vector<int>(cols, 0));
        queue<pair<int, int>> fresh;
        queue<pair<int, int>> rotthisround;
        int possible_max_time = rows * cols;
        int result = 0;
        vector<int> off = {0, 1, 0, -1, 0};

        for (int i=0; i<rows; i++) {
            for (int j=0; j<cols; j++) {
                current[i][j] = grid[i][j];
                if (grid[i][j] == 1) {
                    fresh.push({i, j});
                }
            }
        }

        while (fresh.size() > 0 && result < possible_max_time) {
            int fresh_lastround = fresh.size();
            result++;
            while (fresh_lastround > 0) {
                fresh_lastround--;
                pair<int, int> p = fresh.front();
                fresh.pop();
                int i = p.first;
                int j = p.second;
                if ((i-1 >= 0 && current[i-1][j] == 2) ||
                    (i+1 < rows && current[i+1][j] == 2) ||
                    (j-1 >= 0 && current[i][j-1] == 2) ||
                    (j+1 < cols && current[i][j+1] == 2)
                ){
                    rotthisround.push({i, j});
                    continue;
                }else {
                    fresh.push(p);
                }
            }

            while (rotthisround.size() > 0) {
                current[rotthisround.front().first][rotthisround.front().second] = 2;
                rotthisround.pop();
            }
        }

        if (result >= possible_max_time) {
            return -1;
        }

        return result;
    }
};