rotting_oranges
1from collections import deque 2 3 4# @leet start 5class Solution: 6 def orangesRotting(self, grid: list[list[int]]) -> int: 7 """ 8 This question asks us to count the amount of time it takes for all 9 oranges in a grid to be rotten, where every fresh orange turns rotten 10 if it's next a rotten orange (4-directionally) every minute. 11 12 The way we do this is we first put all of the rotten oranges onto a queue 13 and then have them rot their neighbors. If they can rot any neighbors, 14 add those neighbors to the queue and decrement the count of fresh oranges. 15 16 For each orange, we also enqueue its timestamp, which increments every 17 round. This means we can go round by round without having to re-enqueue 18 any old oranges or having to recopy the queue. 19 20 If we cannot rot any more oranges (there are no more rotten oranges in 21 the queue) then we return the max time if there are no fresh oranges left, 22 otherwise we cannot rot all the fresh oranges and return -1. 23 """ 24 FRESH, ROTTEN = 1, 2 25 m, n = len(grid), len(grid[0]) 26 fresh_oranges = 0 27 q = deque() 28 29 def inbounds(y, x): 30 return 0 <= y < m and 0 <= x < n 31 32 for y in range(m): 33 for x in range(n): 34 if grid[y][x] == FRESH: 35 fresh_oranges += 1 36 elif grid[y][x] == ROTTEN: 37 q.append((y, x, 0)) 38 39 max_time = 0 40 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 41 while q: 42 y, x, time = q.popleft() 43 for dy, dx in dirs: 44 new_y, new_x = dy + y, dx + x 45 if inbounds(new_y, new_x) and grid[new_y][new_x] == FRESH: 46 grid[new_y][new_x] = ROTTEN 47 fresh_oranges -= 1 48 q.append((new_y, new_x, time + 1)) 49 max_time = max(max_time, time + 1) 50 51 return max_time if not fresh_oranges else -1 52 53 54# @leet end 55 56 57def test(): 58 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def orangesRotting(self, grid: list[list[int]]) -> int: 8 """ 9 This question asks us to count the amount of time it takes for all 10 oranges in a grid to be rotten, where every fresh orange turns rotten 11 if it's next a rotten orange (4-directionally) every minute. 12 13 The way we do this is we first put all of the rotten oranges onto a queue 14 and then have them rot their neighbors. If they can rot any neighbors, 15 add those neighbors to the queue and decrement the count of fresh oranges. 16 17 For each orange, we also enqueue its timestamp, which increments every 18 round. This means we can go round by round without having to re-enqueue 19 any old oranges or having to recopy the queue. 20 21 If we cannot rot any more oranges (there are no more rotten oranges in 22 the queue) then we return the max time if there are no fresh oranges left, 23 otherwise we cannot rot all the fresh oranges and return -1. 24 """ 25 FRESH, ROTTEN = 1, 2 26 m, n = len(grid), len(grid[0]) 27 fresh_oranges = 0 28 q = deque() 29 30 def inbounds(y, x): 31 return 0 <= y < m and 0 <= x < n 32 33 for y in range(m): 34 for x in range(n): 35 if grid[y][x] == FRESH: 36 fresh_oranges += 1 37 elif grid[y][x] == ROTTEN: 38 q.append((y, x, 0)) 39 40 max_time = 0 41 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 42 while q: 43 y, x, time = q.popleft() 44 for dy, dx in dirs: 45 new_y, new_x = dy + y, dx + x 46 if inbounds(new_y, new_x) and grid[new_y][new_x] == FRESH: 47 grid[new_y][new_x] = ROTTEN 48 fresh_oranges -= 1 49 q.append((new_y, new_x, time + 1)) 50 max_time = max(max_time, time + 1) 51 52 return max_time if not fresh_oranges else -1
def
orangesRotting(self, grid: list[list[int]]) -> int:
7 def orangesRotting(self, grid: list[list[int]]) -> int: 8 """ 9 This question asks us to count the amount of time it takes for all 10 oranges in a grid to be rotten, where every fresh orange turns rotten 11 if it's next a rotten orange (4-directionally) every minute. 12 13 The way we do this is we first put all of the rotten oranges onto a queue 14 and then have them rot their neighbors. If they can rot any neighbors, 15 add those neighbors to the queue and decrement the count of fresh oranges. 16 17 For each orange, we also enqueue its timestamp, which increments every 18 round. This means we can go round by round without having to re-enqueue 19 any old oranges or having to recopy the queue. 20 21 If we cannot rot any more oranges (there are no more rotten oranges in 22 the queue) then we return the max time if there are no fresh oranges left, 23 otherwise we cannot rot all the fresh oranges and return -1. 24 """ 25 FRESH, ROTTEN = 1, 2 26 m, n = len(grid), len(grid[0]) 27 fresh_oranges = 0 28 q = deque() 29 30 def inbounds(y, x): 31 return 0 <= y < m and 0 <= x < n 32 33 for y in range(m): 34 for x in range(n): 35 if grid[y][x] == FRESH: 36 fresh_oranges += 1 37 elif grid[y][x] == ROTTEN: 38 q.append((y, x, 0)) 39 40 max_time = 0 41 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 42 while q: 43 y, x, time = q.popleft() 44 for dy, dx in dirs: 45 new_y, new_x = dy + y, dx + x 46 if inbounds(new_y, new_x) and grid[new_y][new_x] == FRESH: 47 grid[new_y][new_x] = ROTTEN 48 fresh_oranges -= 1 49 q.append((new_y, new_x, time + 1)) 50 max_time = max(max_time, time + 1) 51 52 return max_time if not fresh_oranges else -1
This question asks us to count the amount of time it takes for all oranges in a grid to be rotten, where every fresh orange turns rotten if it's next a rotten orange (4-directionally) every minute.
The way we do this is we first put all of the rotten oranges onto a queue and then have them rot their neighbors. If they can rot any neighbors, add those neighbors to the queue and decrement the count of fresh oranges.
For each orange, we also enqueue its timestamp, which increments every round. This means we can go round by round without having to re-enqueue any old oranges or having to recopy the queue.
If we cannot rot any more oranges (there are no more rotten oranges in the queue) then we return the max time if there are no fresh oranges left, otherwise we cannot rot all the fresh oranges and return -1.
def
test():