# 994 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:

``````  0          1          2          3          4
2 1 1      2 2 1      2 2 2      2 2 2      2 2 2
1 1 0  =>  2 1 0  =>  2 2 0  =>  2 2 0  =>  2 2 0
0 1 1      0 1 1      0 1 1      0 2 1      0 2 2

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,
• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 10`
• `grid[i][j]` is `0`, `1`, or `2`.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 `````` ``````from collections import deque class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: q = deque() m, n = len(grid), len(grid[0]) total = 0 for i in range(m): for j in range(n): if grid[i][j] == 2: q.append((i, j)) if grid[i][j] > 0: total += 1 if total == 0: return 0 minute = -1 count = 0 while q: minute += 1 q_size = len(q) for _ in range(q_size): count += 1 (x, y) = q.popleft() for d in [(-1, 0), (1, 0), (0, -1), (0, 1)]: x2 = x + d[0] y2 = y + d[1] if ( 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] == 1 ): q.append((x2, y2)) grid[x2][y2] = 2 return minute if count == total else -1``````