I've written out a potential solution to a Leetcode problem but I get this error involving maximum recursion depth. I'm really unsure what I'm doing wrong. Here's what I've tried writing:
def orangesRotting(grid):
R,C = len(grid), len(grid[0])
seen = set()
min_time = 0
def fresh_search(r,c, time):
if ((r,c,time) in seen or r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0):
return
elif grid[r][c] == 2:
seen.add((r,c,0))
elif grid[r][c] == 1:
seen.add((r,c, time 1))
fresh_search(r 1,c,time 1)
fresh_search(r-1,c,time 1)
fresh_search(r,c 1,time 1)
fresh_search(r,c-1,time 1)
for i in range(R):
for j in range(C):
if grid[i][j] == 2:
fresh_search(i,j,0)
for _,_,t in list(seen):
min_time = max(min_time,t)
return min_time
Even on a simple input like grid = [[2,1,1], [1,1,0], [0,1,1]]
. The offending line always appears to be at the if statement
if ((r,c,time) in seen or r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0):
Please note, I'm not looking for help in solving the problem, just understanding why I'm running into this massive recursion issue. For reference, here is the link to the problem. Any help would be appreciated.
CodePudding user response:
So let's trace through what you are doing here. You iterate through the entire grid and if the value for that cell is 2 you call fresh_search
for that cell. We'll start with [0,0]
In fresh_search
you then add the cell with times seen = 0 to your set.
Now for all neighboring cells you call fresh_search
so we'll just look at r 1
. For r 1
your method fresh_search
adds the cell to your set with times seen = 1 and then calls fresh_search
again with all neighboring cells.
Next we'll just look at r-1
which is our origin and now fresh_search
is being called with this cell and times seen = 2. Now this value isn't in the set yet because (0,0,0) != (0,0,2)
so it adds it to the set and again calls fresh_search
with the r 1
cell but now times seen = 3
and so on and so forth until max recursion.