Rotting Oranges (Leetcode 994)
Problem Link: https://leetcode.com/problems/rotting-oranges/
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m=len(grid)
n=len(grid[0])
visited=[[False for i in range(n)] for j in range(m)]
ans=0
q=[]
for i in range(m):
for j in range(n):
if(grid[i][j]==2):
q.insert(0,[i,j,0])
visited[i][j]=True
elif(grid[i][j]==0):
visited[i][j]=True
while(len(q)>0):
curr=q.pop()
curri=curr[0]
currj=curr[1]
currtime=curr[2]
ans=max(ans,currtime)
if(curri-1>=0 and grid[curri-1][currj]==1 and visited[curri-1][currj]==False):
visited[curri-1][currj]=True
q.insert(0,[curri-1,currj,currtime+1])
if(curri+1<m and grid[curri+1][currj]==1 and visited[curri+1][currj]==False):
visited[curri+1][currj]=True
q.insert(0,[curri+1,currj,currtime+1])
if(currj-1>=0 and grid[curri][currj-1]==1 and visited[curri][currj-1]==False):
visited[curri][currj-1]=True
q.insert(0,[curri,currj-1,currtime+1])
if(currj+1<n and grid[curri][currj+1]==1 and visited[curri][currj+1]==False):
visited[curri][currj+1]=True
q.insert(0,[curri,currj+1,currtime+1])
# If any fresh oranges are left, return -1
for i in range(m):
for j in range(n):
if(visited[i][j]==0):
return -1
else:
return ans
Last updated