我的递归 BFS 实现没有提供正确的答案

Question

def riverSizes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    visited = set()
    res = []

    def bfs(row, col, width):
        max_width = width
        directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
        for dr, dc in directions:
            r, c = row + dr, col + dc
            if (r,c) not in visited and r < rows and c < cols and r >= 0 and c >=0 and matrix[r][c] == 1:
                visited.add((r,c))
                max_width = max(bfs(r, c, width + 1), max_width)
        print(max_width)
        return max_width
    
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 1 and (r, c) not in visited:
                visited.add((r, c))
                val = bfs(r, c, 1)
                res.append(val)

    return res

输入：

    [[1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0],
    [1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0],
    [1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1]]

我的输出：[2, 1, 15, 5, 2, 1] 预期输出：[2, 1, 21, 5, 2, 1]

我担心在我的回避分支向多个方向延伸的情况下，它并没有将所有额外的宽度加在一起。

Answer 1

朋友帮我指正说我的方法其实是深度优先搜索。我错误地使用了 max 函数，而我需要做的只是增加宽度和 return 宽度。

def riverSizes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    visited = set()
    res = []

    def dfs(row, col, width):
        directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
        for dr, dc in directions:
            r, c = row + dr, col + dc
            if (r,c) not in visited and r < rows and c < cols and r >= 0 and c >=0 and matrix[r][c] == 1:
                visited.add((r,c))
                width = dfs(r, c, width + 1)
        return width
    
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 1 and (r, c) not in visited:
                visited.add((r, c))
                val = dfs(r, c, 1)
                res.append(val)
    return res

我的递归 BFS 实现没有提供正确的答案

My recursive BFS implemention is not providing the correct answer

python

recursion

breadth-first-search