13

# Rotting Oranges

Difficulty: MEDIUM
Contributed By
Avg. time to solve
20 min
Success Rate
78%

Problem Statement

#### Your task is to find out the minimum time after which no cell has a fresh orange. If it's impossible to rot all the fresh oranges then print -1.

##### Note:
1. The grid has 0-based indexing.
2. A rotten orange can affect the adjacent oranges 4 directionally i.e. Up, Down, Left, Right.
##### Input Format:
The first line of input contains two single space-separated integers 'N' and 'M' representing the number of rows and columns of the grid respectively.

The next 'N' lines contain 'M' single space-separated integers each representing the rows of the grid.
##### Output Format:
The only line of output contains a single integer i.e. The minimum time after which no cell has a fresh orange.

If it's impossible to rot all oranges, print -1.
##### Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
##### Constraints:
1 <= N <= 500
1 <= M <= 500
0 <= grid[i][j] <= 2

Time Limit: 1 sec
3 3
2 1 1
1 1 0
0 1 1
4
##### Explanation of Sample Input 1:
Minimum 4 seconds are required to rot all the oranges in the grid as shown below.

3 3
2 1 0
0 1 1
1 0 1
-1
##### Explanation of Sample Input 2:
The bottom left corner fresh orange (row 2, column 0) has no adjacent oranges. Hence, it's impossible to rot it.
Console