You are given an
m x n
grid where each cell can have one of three values:
0representing an empty cell,
1representing a fresh orange, or
2representing 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
Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4
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.
Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
from collections import deque class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: ROWS, COLS = len(grid), len(grid) 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