### Problem Statement#

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: -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,
``````

### BFS: Iterative#

``````from collections import deque

class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
ans, fresh_count = 0, 0
queue = deque()

# 1) Find all rotten oranges and enque them
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 2:
queue.append((r, c, 0))
elif grid[r][c] == 1:
fresh_count += 1
else:
pass

# 2) BFS through the grid
while queue and fresh_count > 0:
for _ in range(len(queue)):
ro, co, mins = queue.popleft()
mins += 1

# up, right, down, left
for dr, dc in [(-1,0),(0,1),(1,0),(0,-1)]:
r = ro + dr
c = co + dc

if 0 <= r < ROWS and 0 <= c < COLS and grid[r][c] == 1:
grid[r][c] = 2
fresh_count -= 1
ans = max(ans, mins)
queue.append((r, c, mins))

if fresh_count > 0:
return -1
else:
return ans

``````

Leetcode 994 - Rotting Oranges