[Leetcode]994. Rotting Oranges
📄 Description
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-directionally adjacent to a rotten orange becomes rotten.
-1 .Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4Example 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.💻 My Submission
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
R,C =len(grid), len(grid[0])
rotten=[]
# find rotten oranges
for i in range(R):
for j in range(C):
if grid[i][j]==2:
rotten.append((i,j))
minute=0
while rotten:
adj_q=[]
while rotten:
position=rotten.pop(0)
r,c=position[0],position[1]
# check if its neighbor are fresh
if r+1<R and grid[r+1][c]==1:
grid[r+1][c]=2
adj_q.append((r+1,c))
if r-1>=0 and grid[r-1][c]==1:
grid[r-1][c]=2
adj_q.append((r-1,c))
if c+1<C and grid[r][c+1]==1:
grid[r][c+1]=2
adj_q.append((r,c+1))
if c-1>=0 and grid[r][c-1]==1:
grid[r][c-1]=2
adj_q.append((r,c-1))
# if all the adjacent cell got rotten, 1 minute pass
if adj_q:
minute+=1
rotten.extend(adj_q)
# If there is fresh orange left then return -1
for i in range(R):
for j in range(C):
if grid[i][j]==1:
return -1
return minute💊 Better Solution
def orangesRotting(self, grid):
''' Fresh and Rotten Hash Set to track fresh and rotten oranges'''
fresh = set()
rotten = set()
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
fresh.add(str(i) + str(j))
elif grid[i][j] == 2:
rotten.add(str(i) + str(j))
minutes = 0
directions = [[0,1], [1,0], [-1,0], [0,-1]]
"""while fresh oranges exist"""
while fresh:
infected = set()
'''for every rotten orange, check if its neighbors are fresh'''
for orange in rotten:
i = int(orange[0])
j = int(orange[1])
for direction in directions:
nextI = i + direction[0]
nextJ = j + direction[1]
'''if fresh, remove from fresh and add it to infected'''
if (str(nextI) + str(nextJ)) in fresh:
fresh.remove(str(nextI)+str(nextJ))
infected.add(str(nextI) + str(nextJ))
if not infected:
return -1
rotten = infected
minutes += 1
return minuteshttps://leetcode.com/problems/rotting-oranges/
https://leetcode.com/problems/rotting-oranges/discuss/569638/Efficient-Python-Solution-O(N)-Time-Complexity
Reference
この問題について([Leetcode]994. Rotting Oranges), 我々は、より多くの情報をここで見つけました https://velog.io/@limelimejiwon/Leetcode994.-Rotting-Orangesテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol