Untitled

// AMAN JAIN, MCA 1st YEAR 2nd SEM

// time O(N*M), space O(1)
// Approach: Put all rotten oranges in the 0th second stage of grid in a queue
// and then do BFS traversal from rotten oranges in the queue, number of levels
// in the BFS traversal is the amount of time required to rott all fresh oranges
class Solution 
{
    public:
    
    int spreadRott(vector<vector<int>>& grid, queue<pair<int, int>>& cellQueue) {
        int timeSpent = 0, N = grid.size(), M = grid[0].size();
        cellQueue.push({-1, -1}); // level separator
        
        // rotting oranges in BFS traversal
        while(!cellQueue.empty()) {
            int X = cellQueue.front().first;
            int Y = cellQueue.front().second;
            cellQueue.pop();
            if(X == -1 && Y == -1) {
                if(!cellQueue.empty()) {
                    ++timeSpent; // 1 more second to rott next level
                    cellQueue.push({-1, -1}); // level separator
                    continue;
                }
                break;
            }
            if(X + 1 < N && grid[X + 1][Y] == 1) {
                grid[X + 1][Y] = 2;
                cellQueue.push({X + 1, Y});
            }
            if(X - 1 >= 0 && grid[X - 1][Y] == 1) {
                grid[X - 1][Y] = 2;
                cellQueue.push({X - 1, Y});
            }
            if(Y + 1 < M && grid[X][Y + 1] == 1) {
                grid[X][Y + 1] = 2;
                cellQueue.push({X, Y + 1});
            }
            if(Y - 1 >= 0 && grid[X][Y - 1] == 1) {
                grid[X][Y - 1] = 2;
                cellQueue.push({X, Y - 1});
            }
        }
        
        // checking if there is still a fresh orange present
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[i].size(); ++j) {
                if(grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return timeSpent;
    }
    
    //Function to find minimum time required to rot all oranges. 
    int orangesRotting(vector<vector<int>>& grid) {
        int timeSpent = INT_MAX;
        queue<pair<int, int>> cellQueue;
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[0].size(); ++j) {
                if(grid[i][j] == 2) {
                    cellQueue.push({i, j});
                }
            }
        }
        timeSpent = spreadRott(grid, cellQueue);
        return timeSpent;
    }
};