アルゴリズム、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 [] 

Map [x] [y] = '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)