Python Forum
Recursion exit | DFS - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Recursion exit | DFS (/thread-3493.html)



Recursion exit | DFS - BeerLover - May-28-2017

Dear all,

I would very much appreciate some help with the code. It is supposed to find a quickest path towards ".". Like in the game "PacMan". It works now, but when "." is found the program keeps on going through over cells. That messes up the output. Can someone suggest how to exit all the functions which were entered during the search (there is recursion here).
pac_r, pac_c = (3,9)
food_r, food_c = (5,1)
r,c = (7,20)
grid=[]
grid.append(['%','%','%','%','%','%','%','%','%','%','%','%','%','%','%','%','%','%','%','%'])
grid.append(['%','-','-','-','-','-','-','-','-','-','-','-','-','-','-','%','-','-','-','%']) 
grid.append(list("%-%%-%%-%%-%%-%%-%-%"))
grid.append(list("%--------P-------%-%"))
grid.append(list("%%%%%%%%%%%%%%%%%%-%")) 
grid.append(list("%.-----------------%"))
grid.append(list("%%%%%%%%%%%%%%%%%%%%"))
#print(grid[food_r][food_c])

def food(fx,fy):
   if grid[fx][fy] == '.':
       return True 
   else:
       return False
   
visited = []   
def dsf(pac_r,pac_c, food, flag,end):
   # inserting root in stack
   S = [(pac_r,pac_c)]
   if flag==True:
      visited.append((pac_r,pac_c))
   while len(S)>0:
           # v = the current vertex = the last vertex , 
           # or the vertex whose neighboors(=children) we are pushing to stack 
           if end!=True:
               v = S[-1]
               x,y = v
               S.pop()
               print("POP")
               #define neighbors
               neighbors = [] 
               for i in [(x+1,y),(x,y+1),(x,y-1),(x-1,y)]:
                   xx,yy = i 
                   if ( (grid[xx][yy]!='%')&(xx in list(range(0,r)))&(yy in list(range(0,c)))&(i not in visited)):
                       neighbors.append(i)
               #Push all the neighbours of v  that are not visited in stack
               for w in neighbors:
                   nx,ny = w
                   if w not in visited:
                       S.append(w)
                       visited.append(w)
                       if food(nx,ny)==True:
                           print(nx,ny)
                           print(S)
                           print(neighbors)
#                         print("GOTCHA")   ## here I need to exit everything coz I have filled my "array of interest" = visited
                       else: 
                           print(nx,ny,"  ",S,neighbors)
                           dsf(nx,ny,food,False)

dsf(pac_r,pac_c,food,True)