N行N行グリッド内のすべてのパスを計算するためのアルゴリズムです。

Question

私はNxNセルのグリッドを持っています（Array [N] [N]のように定義された2次元配列を考えてください）。

1. なしセルが単一パス以内に2回含まれない：

   どのアルゴリズム各セルに各セルからすべてのパス [I] [J] [K] [L]を計算します。

2. 隣接対角線、水平および垂直方向の動きがすべて合法です。
3. アルゴリズムは平均で最速です。
4. 最小限のメモリが使用されます。

Answer 1

私はあなたが実際のパスを望むと仮定します。

あなたは同じパスで検討頂点にvisitedセットを維持し、すでに同じパスで発見された頂点を模索回避DFSを使用してそれを達成することができます。

擬似コード：

DFS(v,target,visited): 
    if (v == target): 
     print path to v from the initial sorce 
     return 
    visited.add(v) 
    for each vertex u such that u is a neighbor of v: 
     if (u is not in visited): 
      u.parent <- v 
      DFS(u,target,visited) 
    visited.remove(v) 

は[{}が空visited集合である] with DFS(source,target,{})を呼び出します。

Answer 2

幅優先探索は、あなたが望むものとまったく同じです。すべてのパスを生成するときに最も高速ではありません