| 1 | class Solution: |
| 2 | def orangesRotting(self, grid: List[List[int]]) -> int: |
| 3 | q = collections.deque() |
| 4 | fresh = 0 |
| 5 | time = 0 |
| 6 | |
| 7 | for r in range(len(grid)): |
| 8 | for c in range(len(grid[0])): |
| 9 | if grid[r][c] == 1: |
| 10 | fresh += 1 |
| 11 | if grid[r][c] == 2: |
| 12 | q.append((r, c)) |
| 13 | |
| 14 | directions = [[0, 1], [0, -1], [1, 0], [-1, 0]] |
| 15 | while fresh > 0 and q: |
| 16 | length = len(q) |
| 17 | for i in range(length): |
| 18 | r, c = q.popleft() |
| 19 | |
| 20 | for dr, dc in directions: |
| 21 | row, col = r + dr, c + dc |
| 22 | # if in bounds and nonrotten, make rotten |
| 23 | # and add to q |
| 24 | if ( |
| 25 | row in range(len(grid)) |
| 26 | and col in range(len(grid[0])) |
| 27 | and grid[row][col] == 1 |
| 28 | ): |
| 29 | grid[row][col] = 2 |
| 30 | q.append((row, col)) |
| 31 | fresh -= 1 |
| 32 | time += 1 |
| 33 | return time if fresh == 0 else -1 |