この質問はよく見かけますが、通常は、ロボットがたどることができる可能な経路の数だけを見つけることを扱っています。問題は、NxN グリッドがあり、ロボットがグリッドの一番上に立っているということです。一手で右か下にしか動かない。
ここで、ロボットがたどることができるすべてのパスを出力したいと思います。[0][0] から始まる NxN 行列を指定すると、[N-1][N-1] で終了する必要があります。私が試したのは、単純な再帰的ソリューションです。
public static void getPaths(int[][]A, int i, int j, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> allPaths) {
int n = A.length;
if (i>=n || j>=n) return;
if (i==n-1 && j==n-1) {
path.add(A[i][j]);
allPaths.add(new ArrayList<Integer>(path));
return;
}
path.add(A[i][j]);
getPaths(A, i, j+1, path, allPaths);
getPaths(A, i+1, j, path, allPaths);
path.remove(path.size()-1);
}
しかし、現在のパスを「リセット」する場所がわかりません。
たとえば、与えられた
1 2 3
4 5 6
7 8 9
マトリックス、私のソリューションは
[1, 2, 3, 6, 9]
[1, 2, 3, 5, 6, 9]
[1, 2, 3, 5, 6, 8, 9]
[1, 2, 3, 5, 4, 5, 6, 9]
[1, 2, 3, 5, 4, 5, 6, 8, 9]
[1, 2, 3, 5, 4, 5, 6, 7, 8, 9]