You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,1 representing a fresh orange, or2 representing a rotten orange.Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j] is 0, 1, or 2.
class Solution {
public:
int bfs(vector<vector<int>>& grid, int n, int m)
{
queue<pair<int,int>>q;
int count=0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(grid[i][j]==2)q.push({i,j});
}
}
while(!q.empty())
{
int size=q.size();
bool isSpoilt=false;
while(size--)
{
int thisRow=q.front().first;
int thisCol=q.front().second;
q.pop();
int x[4]={-1,1,0,0};
int y[4]={0,0,-1,1};
for(int i=0; i<4; i++)
{
int row=thisRow+x[i];
int col=thisCol+y[i];
if(row>=0 and col>=0 and row<=n-1 and col<=m-1 and grid[row][col]==1)
{
grid[row][col]=2;
q.push({row,col});
isSpoilt=true;
}
}
}
if(isSpoilt)count++;
}
return count;
}
int orangesRotting(vector<vector<int>>& grid) {
int n=grid.size();
int m=grid[0].size();
int ans=bfs(grid,n,m);
for(auto i:grid)
{
for(auto j:i)
{
if(j==1)return -1;
}
}
return ans;
}
};
Office:- 660, Sector 14A, Vasundhara, Ghaziabad, Uttar Pradesh - 201012, India
