# 994. Rotting Oranges from collections import deque """ 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-directionall adjacent to a rotten orange becomes rotten. return the minimum number of minutethat must elapse until no cell has a fresh oragne. if this is impossible, return -1 """ class Solution(object): def orangesRotting(self, grid): """ :type grid: List[List[int]] :rtype: int """ rows = len(grid) if rows == 0: return -1 cols, fresh_cnt, rotten = len(grid[0]), 0, deque() for r in range(rows): for c in range(cols): if grid[r][c] == 2: rotten.append((r, c)) elif grid[r][c] == 1: fresh_cnt += 1 min_pass = 0 while rotten and fresh_cnt > 0: min_pass += 1 for _ in range(len(rotten)): x, y = rotten.popleft() for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: xx, yy = x + dx, y + dy if xx < 0 or xx == rows or yy < 0 or yy == cols: continue if grid[xx][yy] == 0 or grid[xx][yy] == 2: continue fresh_cnt -= 1 grid[xx][yy] = 2 rotten.append((xx, yy)) return min_pass if fresh_cnt == 0 else -1 if __name__ == "__main__": obj = Solution() print(obj.orangesRotting(grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]])) print(obj.orangesRotting(grid=[[2, 1, 1], [0, 1, 1], [1, 0, 1]])) print(obj.orangesRotting(grid=[[0, 2]]))