python - 我可以递增一个变量，将其初始化为 0 作为递归函数中的参数，最后简单地将这个数字附加到数组中吗？

Question

我得到了 matrix仅包含1's和0's ，其中相邻的 1(水平或垂直，而不是对角线)形成 rivers 。我被要求返回 array矩阵中所有河流的大小。

例如

(请注意，河流大小的顺序并不重要 - 它们可以是任何顺序)即 [2,1,2,2,5]也是一个有效的解决方案!

我正在写recursive代码的一部分，当我们探索矩阵时，如果我们偶然发现 1，我们将运行递归来探索其相邻的左、右、上和下中的任何 1。
该代码相当冗长，我认为对于我的问题来说没有必要。我的问题是，当我调用recursive function时，我更新 currentRiverSize +1 (初始化为 0)在递归函数的参数中，当我们偶然发现更多的 1 时，我可以在最后简单地 append这是数组吗？

我感觉递归的结构不正确!

def findAllRiverSizes(matrix): 
    riverSizes = []
    exploreRiver(matrix,row,col,entryExplored,riverSizes,0): 

def exploreRiver(matrix,row,col,entryExplored,riverSizes,currentRiverSize): 
    #look right: 
    if col<len(matrix[0])-1 and not entryExplored[row][col+1] and matrix[row][col+1] == 1: 
        entryExplored[row][col+1] = True
        exploreRiver(matrix,row,col+1,entryExplored,riverSizes,currentRiverSize +1)
    #look left
    if col>0 and not entryExplored[row][col-1] and matrix[row][col-1] == 1: 
        entryExplored[row][col-1] = True
        exploreRiver(matrix,row,col-1,entryExplored,riverSizes,currentRiverSize +1)
    #look up 
    if row >0 and not entryExplored[row-1][col] and matrix[row-1][col]  == 1: 
        entryExplored[row-1][col] = True
        exploreRiver(matrix,row-1,col,entryExplored,riverSizes,currentRiverSize +1)
    #look down
    if row <len(matrix)-1 and not entryExplored[row+1][col] and matrix[row+1][col]  == 1: 
        entryExplored[row+1][col] = True
        exploreRiver(matrix,row+1,col,entryExplored,riverSizes,currentRiverSize +1)
        
    riverSizes.append(currentRiverSize)
    
    return riverSizes

Answer 1

您的代码结构似乎没有按照您所描述的方式进行操作。 一些建议 -

• 不要使用 4 个不同的条件，而是尝试在顶部使用单个条件来检查边界
• 我们可以修改矩阵吗？在这种情况下，我们可以不使用 entryExplored
• 我们不需要将 riverSizes 传递给 DFS 递归函数(因为我们只需在每次 DFS 运行时将值附加到 riverSizes 一次)，因此我们可以让函数返回该值。

这是一个简化的代码，可以完成您想要的操作 -

def findAllRiverSizes(matrix): 
    def exploreRiverDFS(matrix,row,col):
        # go through all neighbors of(row,col) having value 1,
        # set the value to 0(or use entryExplored). In the end after
        # there are no neighbors append the currentRiverSize to riverSizes
        # return the size of this river

        # check if current row, col is valid or there is no river in the current cell
        if (row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[row])
            or matrix[row][col] == 0):
            return 0

        matrix[row][col] = 0
        return 1 + sum([exploreRiverDFS(matrix, row+1, col),
                        exploreRiverDFS(matrix, row-1, col),
                        exploreRiverDFS(matrix, row, col+1),
                        exploreRiverDFS(matrix, row, col-1)])

    riverSizes = []
    
    # iterate through our matrix here, if we come across a 1, call the DFS function
    # to go through all its neighboring cells and set them to 0 in matrix itself
    # if you are allowed to modify matrix(else you can use entryExplored matrix)
    # the exploreRiverDFS function returns the size of current river it traversed through
    
    for row in range(len(matrix)):
            for col in range(len(matrix[row])):
                if matrix[row][col]:
                    riverSizes.append(exploreRiverDFS(matrix, row, col))
    return riverSizes