Untitled

mail@pastecode.io avatarunknown
c_cpp
a month ago
2.3 kB
1
Indexable
Never
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
        vector<vector<bool>> visited(N, vector<bool>(false, M));
        while(!cellQueue.empty()) {
            int X = cellQueue.front().first;
            int Y = cellQueue.front().second;
            cellQueue.pop();
            if(X == -1 && Y == -1) {
                if(!cellQueue.empty()) {
                    ++timeSpent;
                    cellQueue.push({-1, -1}); // level separator
                    continue;
                }
                break;
            }
            if(X + 1 < N && grid[X + 1][Y] == 1 && visited[X + 1][Y] == false) {
                visited[X + 1][Y] = true;
                cellQueue.push({X + 1, Y});
            }
            if(X - 1 >= 0 && grid[X - 1][Y] == 1 && visited[X - 1][Y] == false) {
                visited[X - 1][Y] = true;
                cellQueue.push({X - 1, Y});
            }
            if(Y + 1 < M && grid[X][Y + 1] == 1 && visited[X][Y + 1] == false) {
                visited[X][Y + 1] = true;
                cellQueue.push({X, Y + 1});
            }
            if(Y - 1 >= 0 && grid[X][Y - 1] == 1 && visited[X][Y - 1] == false) {
                visited[X][Y - 1] = true;
                cellQueue.push({X, Y - 1});
            }
        }
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[i].size(); ++j) {
                if(grid[i][j] == 1 && visited[i][j] == false) {
                    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;
    }
};