DFS算法

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 []

当Mapx = 'E‘时，递归不停止并返回p，但它一直持续到末尾。如何纠正它并返回路径(P)。

Answer 1

从外观上看，代码容易无限期地循环。这是因为没有检查您以前是否已经进入节点并从给定节点向所有(4)方向移动。

为了简单地解决这个问题，添加另一个布尔值数组NxN来回答问题：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)