java - 在Java中通过二维数组生成所有路径/路线

Question

我正在使用 Java 工作。给定一个矩阵 NxM，我需要找到通过该数组的所有可能路径。只允许斜向上或斜向下，或向右斜行。 4x4 矩阵示例:

3  5  7  9
2  4  6  8
9  3  7  5
6  8  2  4

矩阵中的数字可以是任意值。我想生成通过矩阵的所有可能的路线，从第一列的四个数字之一开始。只允许向东北、东部和东南方向移动。路线示例:

3-5 7 9
   \
2 4 6-8
9 3 7 5
6 8 2 4

所以所有路线都由 M 个数字组成。我正在使用 2D 数组来保存这个 NxM 矩阵。更多可能的路径是:

3 4 6 5
3 5 6 9
9 4 7 4
9 3 6 9

有没有办法在Java中轻松生成所有路径？

非常感谢任何帮助!

Answer 1

也许您可以使用三种方法来执行此操作并递归调用它们。

1. goNortEast();如果N>0，则向索引[N-1][M+1]搜索元素，否则当前元素的NORtEast将不存在元素，如果元素存在也会导致一条新路径。

2. 向东();每个元素可以按索引 [N][M+1] 向东移动；

3. 去东南();搜索索引[N+1][M+1]处的元素，如果该元素存在，这也会导致一条新路径，

对每个元素调用这三个方法，从 [0][0] 开始，然后 [1][0]，依此类推。

对于[0][0]，它将调用goNorthEast[]-将不满足条件goEast();-index[0][1]和goSouthEast(); index[1][1] 现在调用这些元素的相同三个方法。

最后，您将从您开始的元素中获得所有可能的路径。