## Description

https://leetcode.com/problems/rotting-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, 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`

.

**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:-1Explanation: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:0Explanation:Since there are already no fresh oranges at minute 0, the answer is just 0.

**Constraints:**

`m == grid.length`

`n == grid[i].length`

`1 <= m, n <= 10`

`grid[i][j]`

is`0`

,`1`

, or`2`

.

## Explanation

We can use bread-first search to find out the rotten oranges at each minute.

## Python Solution

```
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
minutes = -1
queue = []
all_empty = True
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 2:
queue.append((i, j))
all_empty = False
elif grid[i][j] == 1:
all_empty = False
if all_empty:
return 0
while queue:
minutes += 1
size = len(queue)
for _ in range(size):
rotten = queue.pop(0)
i = rotten[0]
j = rotten[1]
grid[i][j] = 2
if i - 1 >= 0:
left = (i - 1, j)
if grid[left[0]][left[1]] == 1 and left not in queue:
queue.append(left)
if i + 1 <= len(grid) - 1:
right = (i + 1, j)
if grid[right[0]][right[1]] == 1 and right not in queue:
queue.append(right)
if j - 1 >= 0:
up = (i, j - 1)
if grid[up[0]][up[1]] == 1 and up not in queue:
queue.append(up)
if j + 1 <= len(grid[0]) - 1:
down = (i, j + 1)
if grid[down[0]][down[1]] == 1 and down not in queue:
queue.append(down)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
print (i, j)
return -1
return minutes
```

- Time Complexity: O(N^2).
- Space Complexity: O(N^2).