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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| import collections class Solution(object): def orangesRotting(self, grid): """ :type grid: List[List[int]] :rtype: int """ row, col = len(grid), len(grid[0]) queue = collections.deque() fresh_count = 0 for r in range(row): for c in range(col): if grid[r][c] == 2: queue.append((r, c)) elif grid[r][c] == 1: fresh_count += 1 if fresh_count == 0: return 0 minutes = 0 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue: level_size = len(queue) rotted_in_this_min = False
for _ in range(level_size): (r, c) = queue.popleft() for (dr, dc) in directions: new_r, new_c = dr + r, dc + c if 0 <= new_r < row and 0 <= new_c < col and grid[new_r][new_c] == 1: grid[new_r][new_c] = 2 queue.append((new_r, new_c)) fresh_count -= 1 rotted_in_this_min = True if rotted_in_this_min: minutes += 1 if fresh_count == 0: return minutes else: return -1
|