int orangesRotting(vector<vector<int>>& grid) {
int n= grid.size();
int t;
int m = grid[0].size();
int vis[n][m];
queue<pair<pair<int,int>,int>> q;
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(grid[i][j]==2){
q.push({{i,j},0});
vis[i][j]=2;}
else
vis[i][j]=0;
}
}
int tm=0;
while(!q.empty())
{
int r = q.front().first.first;
int c = q.front().first.second;
t = q.front().second;
tm = max(t,tm);
q.pop();
int drow[] = {0,1,-1,0};
int dcol[] = {1,0,0,-1};
for(int i=0;i<4;++i)
{
int nr = r+drow[i];
int nc = c+dcol[i];
if(nr>=0 && nr<n && nc>=0 && nc<m && vis[nr][nc]!=2 && grid[nr][nc]==1)
{
q.push({{nr,nc},t+1});
vis[nr][nc]=2;
}
}
}
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(grid[i][j]==1 && vis[i][j]!=2)
return -1;
}
}
return tm;
}
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter