0,1行列で再帰的パスを見つける（そしてすべての可能なパスを保存する）java

Question

私は、0,1の値を含むintマトリックス内の位置にバックトラックせずにパスを見つける再帰的メソッドをコーディングしようとしています。 0は踏み込んでも大丈夫ですが、1は大丈夫です。私はまた、50回以上の移動を制限しています。

位置は、行と列の値（x、y）を持つオブジェクトです。 locationEqualsは、2つのLocationsが同じ場合はtrueを返し、そうでない場合はfalseを返す関数です。 マップ変数は、私はパスしようとしています行列はで見つけることです。

private static List<List<Location>> options = new ArrayList<List<Location>>(); 
public static void PathFind(List<Location> path) 
{ 
Location current = path.get(path.size() - 1); 
    boolean done = false; 
    if(locationEquals(current,new Location(24,38))) 
    { 
     options.add(path); 
     return; 
    } 
    if(path.size() > 50) done = true; 
    if(!done) 
    { 
    try 
    { 
    if(map[current.row][current.col + 1] == 0) 
    { 
    if(!path.contains(new Location(current.row, current.col + 1))) 
     { 
      List<Location> temp = path; 
      temp.add(new Location(current.row, current.col + 1)); 
      PathFind(temp); 
     } 
    } 
    } 
    catch (Exception e){} 
      try 
    { 
    if(map[current.row - 1][current.col] == 0) 
    { 
     if(!path.contains(new Location(current.row - 1, current.col))) 
     { 
      List<Location> temp = path; 
      temp.add(new Location(current.row - 1, current.col)); 
      PathFind(temp); 
     } 
    } 
    } 
    catch (Exception e){} 
    try 
    { 
    if(map[current.row][current.col - 1] == 0) 
    { 
     if(!path.contains(new Location(current.row, current.col - 1))) 
     { 
      List<Location> temp = path; 
      temp.add(new Location(current.row, current.col - 1)); 
      PathFind(temp); 
     } 
    } 
    } 
    catch (Exception e){} 
    try 
    { 
    if(map[current.row + 1][current.col] == 0) 
    { 
     if(!path.contains(new Location(current.row + 1, current.col))) 
     { 
      List<Location> temp = path; 
      temp.add(new Location(current.row + 1, current.col)); 
      PathFind(temp); 
     } 
    } 
    } 
    catch (Exception e){} 
    } 

次のコード「オプション」を実行した後、それは方法を見つけることができませんでしたことを意味し、空です。しかし、このマトリックスには確かに方法があるので、私のコードのバグで見つけられません。

Answer 1

問題は、再帰の次のステップに行くたびに新しいリストを作成していないということです（一時変数は実際の一時的なものではなく、パスの参照であり、そのコピーではありません） 。

これを解決するために、私は List<Location> temp = new ArrayList<>(path);

でList<Location> temp = path;を置き換えるので、コードは次のとおりです。

private static List<List<Location>> options = new ArrayList<List<Location>>(); 
public static void PathFind(List<Location> path) { 
    Location current = path.get(path.size() - 1); 
    boolean done = false; 
    if (locationEquals(current, new Location(24, 38))) { 
     options.add(path); 
     return; 
    } 
    if (path.size() > 50) done = true; 
    if (!done) { 
     try { 
      if (map[current.row][current.col + 1] == 0) { 
       if (!path.contains(new Location(current.row, current.col + 1))) { 
        List<Location> temp = new ArrayList<>(path); 
        temp.add(new Location(current.row, current.col + 1)); 
        PathFind(temp); 
       } 
      } 
     } catch (Exception e) { 
     } 
     try { 
      if (map[current.row - 1][current.col] == 0) { 
       if (!path.contains(new Location(current.row - 1, current.col))) { 
        List<Location> temp = new ArrayList<>(path); 
        temp.add(new Location(current.row - 1, current.col)); 
        PathFind(temp); 
       } 
      } 
     } catch (Exception e) { 
     } 
     try { 
      if (map[current.row][current.col - 1] == 0) { 
       if (!path.contains(new Location(current.row, current.col - 1))) { 
        List<Location> temp = new ArrayList<>(path); 
        temp.add(new Location(current.row, current.col - 1)); 
        PathFind(temp); 
       } 
      } 
     } catch (Exception e) { 
     } 
     try { 
      if (map[current.row + 1][current.col] == 0) { 
       if (!path.contains(new Location(current.row + 1, current.col))) { 
        List<Location> temp = new ArrayList<>(path); 
        temp.add(new Location(current.row + 1, current.col)); 
        PathFind(temp); 
       } 
      } 
     } catch (Exception e) { 
     } 
    } 
}