图DFS递归返回值困惑：如何修改代码实现回溯找有效路径

问题描述 #

现有一个网格图，若从左上角单元格(0,0)到右下角单元格(m-1,n-1)的路径中，相邻单元格的数值差小于等于val，则该路径有效。例如当val=2时，存在有效路径1-3-5-3-5，应返回true。

原代码 #

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

问题原因 #

原代码遍历方向时，只要找到一个符合条件的相邻节点就直接递归返回，一旦这条路径走不通就直接返回false，没有尝试其他方向；同时没有在递归失败后将当前节点从seen集合中移除，导致其他路径无法复用该节点，最终错过有效路径。

修改后的代码 #

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:
                # 先判断子递归是否找到有效路径，找到才返回，否则继续遍历其他方向
                if dfs(new_x, new_y):
                    return True
        # 回溯：当前节点所有方向都遍历完，从已访问集合中移除，允许其他路径访问
        seen.remove((x,y))
        return False
    # 启动DFS，从起点(0,0)开始
    return dfs(0, 0)

修改说明 #

• 递归调用子节点时，不再直接返回结果，而是判断子递归是否返回True，只有找到有效路径才返回，否则继续尝试其他方向。
• 增加回溯操作：在遍历完当前节点的所有方向后，将当前节点从seen集合中移除，保证其他分支的路径可以再次访问该节点。
• 补充启动DFS的步骤，原代码未调用dfs(0,0)并返回结果。

内容的提问来源于stack exchange，提问作者Rishika Sankaran