从顶部到网格底部的java路径 [英] java path from top to the bottom of the grid
问题描述
我经常看到这个问题,但它通常只涉及找到机器人可以采取的可能路径的数量。所以,问题是:有NxN网格,机器人站在网格的顶部。在一个动作中,它只能向右或向下移动。
I have seen this question quite often, but it usually deals with finding only the number of the possible paths a robot can take. So, the question is: there is NxN grid, and a robot is standing at the top of the grid. In one move, it can move only to the right or to the bottom.
现在,我想打印出机器人可以采取的所有可能路径。给定一个NxN矩阵,
从[0] [0]开始,它必须以[N-1] [N-1]结束。我试过的是一个简单的递归解决方案:
Now, I would like to print out all the possible paths a robot can take. Given an NxN matrix, starting at [0][0], it has to finish at [N-1][N-1]. What I have tried is a simple recursive solution:
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);
}
但我不知道在哪里重置当前路径。
but I don't know where to "reset" the current path.
让我们说,给定
1 2 3
4 5 6
7 8 9
Let's say, given
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]
matrix, my solution would give
[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]
推荐答案
这应该可以解决问题。输出
This should solve the problem. The output is
[[1, 2, 3, 6, 9], [1, 2, 5, 6, 9], [1, 2, 5, 8, 9], [1, 4, 5, 6, 9], [1, 4, 5, 8, 9], [1, 4, 7, 8, 9]]
。
public class Main {
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;
path.add(A[i][j]);
if (i==n-1 && j==n-1) {
allPaths.add(path);
return;
}
getPaths(A, i, j+1, new ArrayList<>(path), allPaths);
getPaths(A, i+1, j, path, allPaths);
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> allPaths = new ArrayList<>();
getPaths(new int[][] { {1,2,3},{4,5,6},{7,8,9}}, 0,0, new ArrayList<Integer>(), allPaths );
System.out.println(allPaths);
}
}
这篇关于从顶部到网格底部的java路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!