Description
https://leetcode.com/problems/rotting-oranges/
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, or2representing 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 -1.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4
Example 2:
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.
Example 3:
Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]is0,1, or2.
Explanation
We can use bread-first search to find out the rotten oranges at each minute.
Python Solution
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
minutes = -1
queue = []
all_empty = True
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 2:
queue.append((i, j))
all_empty = False
elif grid[i][j] == 1:
all_empty = False
if all_empty:
return 0
while queue:
minutes += 1
size = len(queue)
for _ in range(size):
rotten = queue.pop(0)
i = rotten[0]
j = rotten[1]
grid[i][j] = 2
if i - 1 >= 0:
left = (i - 1, j)
if grid[left[0]][left[1]] == 1 and left not in queue:
queue.append(left)
if i + 1 <= len(grid) - 1:
right = (i + 1, j)
if grid[right[0]][right[1]] == 1 and right not in queue:
queue.append(right)
if j - 1 >= 0:
up = (i, j - 1)
if grid[up[0]][up[1]] == 1 and up not in queue:
queue.append(up)
if j + 1 <= len(grid[0]) - 1:
down = (i, j + 1)
if grid[down[0]][down[1]] == 1 and down not in queue:
queue.append(down)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
print (i, j)
return -1
return minutes
- Time Complexity: O(N^2).
- Space Complexity: O(N^2).