13

Rotting Oranges

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

Problem Statement

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

  • Value 0 - representing an empty cell.
  • Value 1 - representing a fresh orange.
  • Value 2 - representing a rotten orange.
  • Every second, any fresh orange that is adjacent(4-directionally) to a rotten orange becomes rotten.

    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
    
    Sample Input 1:
    3 3
    2 1 1
    1 1 0
    0 1 1 
    
    Sample Output 1:
    4
    
    Explanation of Sample Input 1:
    Minimum 4 seconds are required to rot all the oranges in the grid as shown below.
    

    alt text

    Sample Input 2:
    3 3
    2 1 0
    0 1 1
    1 0 1
    
    Sample Output 2:
    -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.
    
    Reset Code
    Full screen
    copy-code
    Console