74 lines
1.7 KiB
Markdown
74 lines
1.7 KiB
Markdown
|
---
|
||
|
|
layout: page
|
||
|
|
title: Rotton Oranges
|
||
|
|
---
|
||
|
|
|
||
|
|
This is a BFS problem in disguise. You also need to think carefully about which variables you need to keep track of.
|
||
|
|
|
||
|
|
IE: minutes_passed and fresh_count and going thru the grid once to get rotton cells.
|
||
|
|
|
||
|
|
{% highlight python %}
|
||
|
|
|
||
|
|
grid = [[2,1,1],[1,1,0],[0,1,1]]
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
def orangesRotting(grid):
|
||
|
|
|
||
|
|
R = len(grid)
|
||
|
|
C = len(grid[0])
|
||
|
|
|
||
|
|
fresh_count=0
|
||
|
|
|
||
|
|
# get all cells with rotton oranges
|
||
|
|
rottonQueue = []
|
||
|
|
for i in range(R):
|
||
|
|
for j in range(C):
|
||
|
|
if grid[i][j]==2:
|
||
|
|
rottonQueue.append( (i,j) )
|
||
|
|
elif grid[i][j]==1:
|
||
|
|
fresh_count+=1
|
||
|
|
|
||
|
|
minutes_passed = 0
|
||
|
|
|
||
|
|
while rottonQueue and fresh_count>0:
|
||
|
|
|
||
|
|
minutes_passed+=1
|
||
|
|
|
||
|
|
# process orange at the current level
|
||
|
|
for i in range(len(rottonQueue)):
|
||
|
|
|
||
|
|
# get rotton
|
||
|
|
x, y = rottonQueue.pop(0)
|
||
|
|
|
||
|
|
# visit neighbours
|
||
|
|
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
|
||
|
|
|
||
|
|
# calculate coordinates of adjacent cells
|
||
|
|
xx, yy = x+dx, y+dy
|
||
|
|
|
||
|
|
# ignore cell if it's out of boundary
|
||
|
|
if xx<0 or xx==R or yy<0 or yy==C:
|
||
|
|
continue
|
||
|
|
|
||
|
|
# ignore cell if it is empty '0' or visited before '2'
|
||
|
|
if grid[xx][yy]==0 or grid[xx][yy]==2:
|
||
|
|
continue
|
||
|
|
|
||
|
|
# update fresh count
|
||
|
|
fresh_count-=1
|
||
|
|
|
||
|
|
# mark current cell as rotton
|
||
|
|
grid[xx][yy]=2
|
||
|
|
|
||
|
|
# add to queue
|
||
|
|
rottonQueue.append((xx,yy))
|
||
|
|
|
||
|
|
return minutes_passed if fresh_count==0 else -1
|
||
|
|
|
||
|
|
print( orangesRotting(grid) )
|
||
|
|
|
||
|
|
{% endhighlight %}
|
||
|
|
|
||
|
|
|
||
|
|
![image1]()
|