Rotten Oranges

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,
• 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.

Note for C++ and Java: You should not use Pair.

Input Format

First Parameter - Matrix grid of size m x n

Output Format

Return the number

Example 1:

Input: 
    3 3
    2 1 1        
    1 1 0
    0 1 1
Output: 4
Explanation: 3 3 represents the size of the grid. Minimum number of minutes until no cell has fresh oranges is 4. 

Example 2:

Input:
    3 3
    2 1 1        
    0 1 1
    1 0 1
Output: -1
Explanation: 3 3 represents the size of the grid. The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1 or 2
• Expected Time Complexity: O(n²)
• Expected Space Complexity: O(n²)