我编写了一个程序来递归地在 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)。
最佳答案
从表面上看,代码很容易无限循环。这是由于缺乏检查您之前是否已进入节点并从给定节点向所有 (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)
关于算法,深度优先,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36837705/