Untitled
unknown
c_cpp
a year ago
2.5 kB
12
Indexable
Never
// 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; } };