Rotten Oranges Efficient Code
In this class, We discuss Rotten Oranges Efficient Code.
Readers can prepare a full competitive coding course to crack product development companies. Click Here.
The reader should have basic coding skills to work with competitive coding. Click here.
Question:
Given a matrix of dimension M X N.
Each cell in the matrix can have numbers 0, 1, or 2.
0 means no orange in the cell.
1 means fresh orange in the cell
2 means rotten orange in the cell
A rotten orange in cell i,j can rot the orange present in the left, right, up, and down cells in one second.
Our task is to find the time required to rot all the oranges in the matrix.
If all the oranges can not be rotten, then we display -1.
You can understand the question better with an example.
The example and the step-by-step logic explanation are provided in the video.
Code:
class Solution:
def issafe(self,i, j,R,C):
if (i >= 0 and i < R and j >= 0 and j < C):
return True
return False
def orangesRotting(self, v):
q=[]
r=len(v)
c=len(v[0])
for i in range(r):
for j in range(c):
if(v[i][j]==2):
x=[]
x.append(i)
x.append(j)
q.append(x)
q.append([-1,-1])
count=0
while(len(q)!=0):
z=q.pop(0)
if(z[0]!=-1 and z[1]!=-1):
i=z[0]
j=z[1]
if(v[i][j]==2):
if(self.issafe(i+1,j,r,c) and v[i+1][j]==1):
v[i+1][j]+=1
q.append([i+1,j])
if(self.issafe(i,j+1,r,c) and v[i][j+1]==1):
v[i][j+1]+=1
q.append([i,j+1])
if(self.issafe(i-1,j,r,c) and v[i-1][j]==1):
v[i-1][j]+=1
q.append([i-1,j])
if(self.issafe(i,j-1,r,c) and v[i][j-1]==1):
v[i][j-1]+=1
q.append([i,j-1])
else:
if(len(q)>0):
q.append([-1,-1])
count+=1
for i in range(r):
for j in range(c):
if(v[i][j]==1):
return -1
return count
v=[[2,2,0,1]]
ob=Solution()
k=ob.orangesRotting(v)
print(k)