My recursive BFS implemention is not providing the correct answer-CodePudding

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

Input:

    [[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]]

My output: [2, 1, 15, 5, 2, 1] Expected output: [2, 1, 21, 5, 2, 1]

I am concerned that in the case where my recusion branches out in multiple directions, it isn't adding all the additional widths together.

CodePudding user response：

I was helped by friend who corrected me that my approach is actually Depth First Search. I was mistakenly using the max function when instead all I needed to do was increment the width and return the width.

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