我可以增加一個變數，初始化為0作為遞回函式中的引數，最后簡單地將此數字附加到陣列中嗎？

我得到一個matrix只包含1'sand 0's，其中相鄰的 1（水平或垂直，不是對角線）形成rivers。我被要求回傳array矩陣中所有河流大小的一個。

例如

（注意河流大小的順序無關緊要 - 它們可以按任何順序排列）即[2,1,2,2,5]也是一個有效的解決方案！

我正在撰寫recursive代碼的一部分，當我們探索矩陣時，如果我們偶然發現一個 1，我們將運行一個遞回來探索它相鄰的左、右、上和下的任何 1。
代碼很長，我認為我的問題沒有必要。我的問題是，當我呼叫recursive function, 并且currentRiverSize 1當我們偶然發現更多 1 時，我更新（初始化為 0）遞回函式的引數，然后我可以在最后簡單地將appendthis 到陣列嗎？

我有一種感覺，遞回結構不正確！

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

uj5u.com熱心網友回復：

您的代碼結構似乎沒有按照您所描述的那樣做。一些建議——

• 嘗試使用頂部的單個條件來檢查邊界，而不是使用 4 個不同的條件
• 我們可以修改矩陣嗎？在這種情況下，我們可以不用entryExplored
• 我們不需要將 傳遞riverSizes給 DFS 遞回函式（因為我們只需要在riverSizes每次 DFS 運行時將值附加到一次），因此我們可以讓函式回傳該值。

這是一個簡化的代碼，可以滿足您的需求-

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

標籤：Python 递归

上一篇：如何在SQL中覆寫過去的記錄？

下一篇：如何僅使用遞回解決磁區問題