java - 如何在多维数组中找到所有可能的递增顺序路径？

Question

我想知道 Java 代码以找到多维数组的所有可能路径。我们应该从[0][0]节点开始，往前走。要记住的是，无论元素顺序如何，路径都必须按递增顺序排列。如果下一个元素等于（或小于）当前元素，我们不应该遍历。

示例数组：

3   5   1
6   7   4
8   2   9

结果：

3,5,6,7,8
3,5,6,7,9
3,5,7,8
3,5,7,9
3,6,7,8
3,6,7,9
3,7,8
3,7,9

Answer 1

您应该从起点开始构建一棵树。在您的示例数组中，从左上角开始，树可能如下所示：

     3
   / \ \ 
  5  6  7 
 / \  \  \
7   6  ..  ..

一旦你有了那棵树，你只需要走下树中的每条路径。

尽管它可能看起来很吓人，但您可以将其分为两部分：

• 构建树。
• 遵循路径。

---

• 首先，尝试想出一种方法来让您的起点开始打印。这很容易。

• 一旦你做到了那么远，打印你的起点的邻居>它的价值。

• 然后，为每个邻居做同样的事情！

Answer 2

我认为以下代码可以满足您的描述。它开始检查第一个节点 (0,0)。对于检查的每个节点，都会创建一个邻居向量。邻居是有资格成为路径延续的节点（即表中具有较高值的​​相邻节点）。然后对于每个邻居，克隆路径，并检查新邻居。这一直持续到被检查节点没有合格的邻居，此时路径被打印并且算法终止。

尝试这个：

import java.util.Arrays;
import java.util.Vector;

class Main {
  class Coords {
    int x;
    int y;
    Coords(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
  int [][] array = { {3,5,1},{6,7,4},{8,2,9}};
  Vector<Coords> getNeighbors(Coords coords) {
     int x = coords.x;
     int y = coords.y;
     Vector<Coords> result = new Vector<Coords>();
     if (x < array.length - 1) {
        if (array[x + 1][y] >= array[x][y])
          result.add(new Coords(x + 1, y));
     }
     if (x > 0) {
        if (array[x - 1][y] >= array[x][y])
          result.add(new Coords(x - 1, y));
     }
     if (y < array[x].length - 1) {
        if (array[x][y + 1] >= array[x][y])
          result.add(new Coords(x, y + 1));
     }
     if (y > 0) {
        if (array[x][y - 1] >= array[x][y])
          result.add(new Coords(x, y - 1));
     }
     if (x < (array.length - 1 ) &&  (y < array[x].length - 1)) {
        if (array[x + 1][y + 1] >= array[x][y])
          result.add(new Coords(x + 1, y + 1));
     }
     if (x < (array.length - 1 ) &&  (y > 0)) {
        if (array[x + 1][y - 1] >= array[x][y])
          result.add(new Coords(x + 1, y - 1));
     }
     if (x > 0 &&  (y < array[x].length - 1)) {
        if (array[x - 1][y + 1] >= array[x][y])
          result.add(new Coords(x - 1, y + 1));
     }
     if (x > 0 &&  y > 0) {
        if (array[x -1][y - 1] >= array[x][y])
          result.add(new Coords(x - 1, y - 1));
     }
     return result;
  }
  void checkNode(Vector<Integer> path, Coords coords) {
    path.add(array[coords.x][coords.y]);
    Vector<Coords> neighbors = getNeighbors(coords);
    if (neighbors.size() == 0) {
       for (Integer i : path) {
         System.out.print(i+"\t");
       }
       System.out.println();
    }
    for (Coords c : neighbors) {
      Vector<Integer> newpath = (Vector<Integer>) path.clone();
      checkNode(newpath, c);
    }
  }
  Main() {
    System.out.println ("Array: " + Arrays.deepToString(array));
    checkNode(new Vector<Integer>(),new Coords(0,0));
  }

  public static void main(String args[]) {
    new Main();
  }
}

输出：

Array: [[3, 5, 1], [6, 7, 4], [8, 2, 9]]
3   6   8   
3   6   7   9   
3   6   7   8   
3   5   7   9   
3   5   7   8   
3   5   6   8   
3   5   6   7   9   
3   5   6   7   8   
3   7   9   
3   7   8   

它还为我提供了路径 3、6、8，这不在您的示例输出中