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