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) |