DFS 最终陷入无限循环

Question

我写了一个dfs搜索来解决一个问题。我要解决的问题是，当给定一个数字数组（例如 [2, 1, 3]）时，我需要迭代该数组并计算其本身及其相邻单元格（如果已填充）。例如，如果数组是 [2, 1, 3]，则答案将是 [1, 2, 3]。如果数组是 [1, 4, 2, 5]，那么答案就是 [1, 1, 2, 2]。

这就是我所拥有的：

def 解决方案（查询）： 长度 = 最大(查询)+1 区 = [0] * 长度

def dfs(spot, district):
    if spot < 0 or spot >= len(district) or district[spot] == 0:
        return 0
    return 1 + dfs(spot-1, district) + dfs(spot+1, district)
res = []
for q in queries:
    district[q] = 1
    curr = dfs(q, district)
    res.append(curr)
return res

不知何故，我的 dfs 函数最终陷入了无限循环。有什么建议可以解决这个问题吗？

谢谢。

不知何故，我的 dfs 函数最终陷入了无限循环。有什么建议可以解决这个问题吗？

Answer 1

我可以看到所访问的单元格没有标记，这将允许 DFS 算法一次又一次地访问同一单元格，从而导致无限循环。遍历单元格后，只需将其标记为已访问即可。比如：

def solution(queries):
    length = max(queries)+1
    district = [0] * length

    def dfs(spot, district):
        if spot < 0 or spot >= len(district) or district[spot] == 0:
            return 0
        district[spot] = 0  # <----- Here
        return 1 + dfs(spot-1, district) + dfs(spot+1, district)

    res = []
    for q in queries:
        district[q] = 1
        curr = dfs(q, district)
        res.append(curr)
    return res