leetocde 505 请帮忙诊断我的DFS解法

leetocde 505
请大家帮忙看看，为何我的DFS的解法不对。 可以通过example的test case， 在提交后，不能通过。 很想知道自己的问题在哪里，找到自己逻辑上的根本原因。
  def shortestDistance(self, grid: List[List[int]], start: List[int], des: List[int]) -> int:
        dirs = [(0,1), (0,-1), (1,0), (-1,0)]
        dst = {}
        def next_pos(x, y, dx, dy):
            moves = 0
            while 0 <= x + dx < len(grid) and 0 <= y + dy < len(grid[0]) and grid[x + dx][y + dy] == 0:
                x += dx
                y += dy
                moves += 1
            return x, y, moves
        def dfs(grid, x, y):
            if [x, y] == des:
                return 0
            if (x, y) in dst:
                return dst[(x, y)]
            dst[(x, y)] = float('inf')
            res = float('inf')
            for dx, dy in dirs:
                new_x, new_y, moves = next_pos(x, y, dx, dy)
                cur =  dfs(grid, new_x, new_y)
                res = min(cur + moves, res)
                print((x, y), (new_x, new_y), cur, res)
            dst[(x, y)] = res
            return res
        res = dfs(grid, start[0], start[1])
        
        return -1 if res == float('inf') else res

作用不一样。你这个代码的bug在与这个dst在DFS完成所有neighbor遍历结束前就被有可能已经被设置为float('inf')了 。这就导致你正在DFS一个path的时候，当你到达一个已开始但未完成搜索的cell时，DFS会误认为它发现了一个循环。你的dst实际上可以减少一部分冗余计算，但是不能启到visited set避免cycling的作用。

你的dfs没有标记visited会死循环。

九道 发表于 2023-10-3 10:27
你的dfs没有标记visited会死循环。

谢谢您的留言。我有一个变量dst，记录访问过的点， 类似visit的。目前尚未出现死循环的提示

九道 发表于 2023-10-3 14:20
作用不一样。你这个代码的bug在与这个dst在DFS完成所有neighbor遍历结束前就被有可能已经被设置为float('in ...

好像明白我的逻辑漏洞在那里啦，谢谢您的点拨！