算法，深度优先

Question

我编写了一个程序来递归地在 N*N 网格中查找最短路径。

def dfs(x,y,Map,p):
    N = len(Map)
    p += [[x,y]]
    if Map[x][y] == 'E':
        return p

    for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        if N > i[0] >= 0 and N > i[1] >= 0 :
            if (Map[i[0]][i[1]] == 'P' or Map[i[0]][i[1]] == 'E')  and i not in p:
                dfs(i[0], i[1], Map,p)
    return []

当 Map[x][y] = 'E' 时，递归不会停止并返回 p。但它一直持续到最后。如何更正它并返回路径(p)。

Answer 1

从表面上看，代码很容易无限循环。这是由于缺乏检查您之前是否已进入节点并从给定节点向所有 (4) 个方向移动。

为了简单地解决它，添加另一个 NxN 的 bool 值数组来回答问题:visited?。然后将代码更新为以下几行:

def dfs(x,y,Map,visited,p):
    visited[x,y] = true;
    N = len(Map)
    (...)
    if (Map[i[0]][i[1]] == 'P' or Map[i[0]][i[1]] == 'E')  
        and i not in p
        and visited[i[0], i[1]] == false:
        dfs(i[0], i[1], Map,visited,p)