Untitled

unknown
c_cpp
a year ago
2.3 kB
2
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});
}
}
}