python - 岛大小问题给出最大递归深度误差

Question

我正在解决查找 nxm 矩阵中存在的所有岛的大小的问题。我使用了递归方法，不知道我的代码中的错误是什么导致了最大递归深度错误。先感谢您 ：）

def riverSizes(matrix):
    returnList = []
    for row in range(len(matrix)):
        for column in range(len(matrix[row])):
            if matrix[row][column] == 1:
                returnList.append(visitConnected(matrix,row,column))
                
def visitConnected(matrix,row,column,size=0):
    if inBounds(row,column,matrix):
        if matrix[row][column] == 1:
            matrix[row][column] == -1
            size += 1
            size += visitConnected(matrix,row +1,column)
            size += visitConnected(matrix,row - 1,column)
            size += visitConnected(matrix,row,column+1)
            size += visitConnected(matrix,row,column-1)
        else:
            return size
    else:
        return size

        
def inBounds(row,column,matrix):
    return row >= 0 and row < len(matrix) and column >= 0 and column < len(matrix[0])

标签： pythonrecursiongaps-and-islands

Answer 1

在没有看到示例或调用的情况下，我至少可以看到一个问题。考虑矩阵[[1, 1]]。 visitConnected(..., 0, 0)will call size += visitConnected(..., 0, 1)， which will call size += visitConnected(..., 0, 0)，所以你永远不会终止。

你写matrix[row][column] == -1而不是matrix[row][column] = -1，所以那里什么也没有发生。您也不会返回最终尺寸，因此您的退货清单将是 all None。