Python在2darray中迭代

Question

我有一个2D数组，比如

    grid = [[1, 0, 0, 0, 0], 
            [0, 0, 0, 0, 0], 
            [0, 0, 0, 0, 0]]

现在，基于存在1的点，我想创建一个新数组，并保存到所有点的距离。范例

dp = [[1, 2, 3, 4, 5], 
      [2, 3, 4, 5, 6], 
      [3, 4, 5, 6, 7]]

我不知道我错过了什么

def minTotalDistance(grid):
    dp = [[0]*len(grid[0]) for _ in range(len(grid))]

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                dfs(i, j, dp, 1)
                
    print dp 
    
def dfs(i, j, dp, val): 
    if i < 0 or i >= len(dp) or j < 0 or j >= len(dp[0]):
        return 0 
    dp[i][j] = val
    dfs(i - 1, j, dp, val+1)
    dfs(i + 1, j, dp, val+1)
    dfs(i, j - 1, dp, val+1)
    dfs(i, j + 1, dp, val+1)
    

grid = [[1, 0, 0, 0, 1], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]]
minTotalDistance(grid)

Answer 1

我认为这里的问题在于递归调用。例如，当您调用dfs(0, 0, dp, val)时，它将调用dfs(0-1, 0, dp, val)返回，但随后它将调用dfs(1, 0, dp, val)，然后调用dfs(1 - 1, 0, dp, val)。这里dp和val在递归方面是不相关的，因为它们不会以任何方式终止函数。请注意，最后一个调用相当于第一个调用，即i和j，它们只是重复这个循环，直到调用堆栈超出内存边界，您就会得到错误

Answer 2

当您使用递归时，必须确保永远不要进入递归循环，其中递归函数使用一些参数调用自身，在该调用中，使用原始参数再次调用自身

这里，当计算df(i, j, ...)时，您调用dfs(i-1, j, ...)，在该调用中，您有dfs(i+1, j, ...)，它给出了原始点=>；无限循环

您应该确保始终增加索引，或者为未初始化的点设置一个不同的值，并在点已经收到值后立即中断递归

Answer 3

您需要一些条件来停止递归。例如，仅处理未处理的单元格或当前路径构成改进的单元格

def dfs(i, j, dp, val): 
    if  not (0 <= i < len(dp) and 0 <= j < len(dp[0])):
        return 0 
    # only process if improvement or unprocessed
    if dp[i][j] == 0 or val < dp[i][j]: 
        dp[i][j] = val
        dfs(i - 1, j, dp, val+1)
        dfs(i + 1, j, dp, val+1)
        dfs(i, j - 1, dp, val+1)
        dfs(i, j + 1, dp, val+1)