// 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;
}
};