Graph DFS - Confused about the return value of recursion

Question

I have a graph where a path from top-left cell - (0,0) to the bottom-right cell - (m-1,n-1) is valid if the difference between consecutive cells are less than or equal to "val".

For instance, this example should return true for a val=2 because there is a valid path: 1-3-5-3-5

m,n = len(graph), len(graph[0])
dirs = [(0,-1),(-1,0),(0,1),(1,0)]

def isValidPos(x,y, seen):
            return 0<=x<m and 0<=y<n and (x,y) not in seen

def isValidPath(val):
            seen = set()
            def dfs(x,y):
                if x==m-1 and y==n-1:
                    return True
                seen.add((x,y))
                for dx,dy in dirs:
                    new_x, new_y = x+dx, y+dy
                    if isValidPos(new_x, new_y, seen) and abs(graph[new_x][new_y]-graph[x][y])<=val:
                        return dfs(new_x,new_y)
                return False

My code for the dfs from (0,0) is as follows. The result returned is False. I understand that 1-2-2-2-5 returns False, but it should explore another path instead of returning False directly. How do I change my code to backtrack instead of returning False ?

Answer 1

your dfs(x,y) function returns False on the first failure valid attemp:

if isValidPos(new_x, new_y, seen) and abs(graph[new_x][new_y]-graph[x][y])<=val:
                        return dfs(new_x,new_y)

instead, you should return True only at the first success:

if isValidPos(new_x, new_y, seen) and abs(graph[new_x][new_y]-graph[x][y])<=val:
                        if dfs(new_x,new_y): return True