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, or
	2 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.

&nbsp;
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.


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 10
	grid[i][j] is 0, 1, or 2.


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        visited = set()
        res = 0
        def bfs(grid):
            que = collections.deque()
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == 2:
                        que.append((i,j))
            que.append(None)
            count = 0    
            while len(que)>0:
                left , right = 0,0
				# This other while loop is to make sure that we traverse from all the rotten oranges in one turn.
                while que[0] != None:
                    r,c = que.popleft()
                    for Cols in [-1,1]:
                        if c+Cols>=0 and c+Cols<len(grid[0]) and grid[r][c+Cols]==1:
                            grid[r][c+Cols] = 2
                            left += 1
                            que.append((r,c+Cols))
                    
                    for Rows in [-1,1]:
                        if r+Rows>=0 and r+Rows<len(grid) and grid[r+Rows][c]==1:
                            grid[r+Rows][c] = 2
                            right += 1
                            que.append((r+Rows,c))
				'''
				if either left or right or both is incremented it means that we have moved in either direction,
				and then this will be counted as a turn(or minute as per the problem description.).
				
				'''
                if left is not 0 or right is not 0:
                    count+=1
                que.popleft()
                if len(que)>0:
				    '''
				    This is required to terminate the loop and prevent infinite loop.
				    This only appends a None if there is still some values in the que, 
				    else we have completed our traversal and we can stop going any futher.
				    '''
                    que.append(None)
            return count
        res = bfs(grid)
        for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == 1:
                        return -1
        return res
class Solution {
    class Pair{
        int i;
        int j;
        int t;
        
        public Pair(int i,int j,int t){
            this.i = i;
            this.j = j;
            this.t = t;
        }
    }
    int ans = 0;
    final int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    public int orangesRotting(int[][] grid) {
        int countFresh = 0;
        Queue<Pair> q = new LinkedList<>();
        for(int i=0;i<grid.length;i++){
            for(int j = 0;j<grid[0].length;j++){
                if(grid[i][j] == 2){
                    q.offer(new Pair(i,j,0));
                }else if(grid[i][j] == 1){
                    countFresh++;
                }
            }
        }
        int count = 0;
        while(q.size() != 0){
            Pair temp = q.poll();
            ans = Math.max(ans,temp.t);
            for(int[] d : dir){
                int r = temp.i + d[0];
                int c = temp.j + d[1];
                int t = temp.t +1;
                if(r >= 0 && c >= 0 && r <grid.length && c < grid[0].length && grid[r][c] == 1){
                    q.offer(new Pair(r,c,t));
                    grid[r][c] = 2;
                    count++;
                }
            }
        }
        if(count != countFresh) return -1;
        return ans;
    }
}
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int R = grid.size();
        int C = grid[0].size();
        queue<vector<int>> nextOrangesToRot;
        for(int r = 0; r < R; ++r)
            for(int c = 0; c < C; ++c)
                if(grid[r][c] == 2)
                    nextOrangesToRot.push({r, c});
        
        vector<int> xDir {-1, 0, 0, 1};
        vector<int> yDir {0, 1, -1, 0};
        int totalTime = 0;
        while(!nextOrangesToRot.empty())
        {
            int size = nextOrangesToRot.size();
            while(size--)
            {
                vector<int>& currOrangeCell =  nextOrangesToRot.front();
                
                for(int i = 0; i < 4; ++i)
                {
                    int nextR = currOrangeCell[0] + xDir[i];
                    int nextC = currOrangeCell[1] + yDir[i];
                    if(nextR >= 0 && nextR < R && 
                       nextC >= 0 && nextC < C && grid[nextR][nextC] == 1)
                    {
                        grid[nextR][nextC] = 2; //rotted
                        nextOrangesToRot.push({nextR, nextC});
                    }
                }
                nextOrangesToRot.pop();
            }
            if(nextOrangesToRot.size())
                totalTime++;
        }
        for(int r = 0; r < R; ++r)
            for(int c = 0; c < C; ++c)
                if(grid[r][c] == 1)
                   return -1;
        return totalTime;
    }
};
let convertAdjacentCellsToRotten = (grid, locations, rottenOranges) => {
    let didConvertAny = false;
    let newLocations = [];
    for(let i=0;i<locations.length;i++){
        let loci = locations[i][0]
        let locj = locations[i][1]
        
        if(loci+1 < grid.length && grid[loci+1][locj] === 1) {
            grid[loci+1][locj] = 2;
            newLocations.push([loci+1,locj])
            didConvertAny = true;
            rottenOranges++
        }
        if(loci-1 >= 0 && grid[loci-1][locj] === 1) {
            grid[loci-1][locj] = 2;
            newLocations.push([loci-1,locj])

            didConvertAny = true;
            rottenOranges++
        }
        if(locj+1 < grid[0].length && grid[loci][locj+1] === 1) {
            grid[loci][locj+1] = 2;
            newLocations.push([loci,locj+1])
            didConvertAny = true;
            rottenOranges++
        }
        if(locj-1 >= 0 && grid[loci][locj-1] === 1) {
            grid[loci][locj-1] = 2;
            newLocations.push([loci,locj-1])
            didConvertAny = true;
            rottenOranges++
        }
    }
    
    return {didConvertAny:didConvertAny, rottenOranges,locations:[...newLocations]}
}
var orangesRotting = function(grid) {
    let rottenLocation = [];
    let rottenOranges = 0;
    let totalOranges = 0;
    let minutes = 0;
    for(let i=0;i<grid.length;i++) {
        for(let j=0;j<grid[0].length;j++) {
            if(grid[i][j]===2) {
                rottenLocation.push([i,j])
                rottenOranges++;
            }
            if(grid[i][j]!==0) totalOranges++;
        }
    }
    
    while (1) {
        let gridConversionResult = convertAdjacentCellsToRotten(grid,rottenLocation,rottenOranges);
        if (gridConversionResult.didConvertAny) {
            rottenLocation = gridConversionResult.locations;
            minutes++;
            rottenOranges = gridConversionResult.rottenOranges;
        }
        else break
    }
    if(totalOranges===rottenOranges) return minutes;
    else return -1
    
};
Rotting Oranges