-7

多次元配列のすべての可能なパスを見つけるための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
4

2 に答える 2

1

開始点から始めて、ツリーを構築する必要があります。例の配列では、左上から始めて、ツリーは次のようになります。

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

そのツリーを取得したら、ツリー内の各パスをステップダウンする必要があります。

威圧的に見えるかもしれませんが、これを2つの部分に分けることができます。

  • ツリーを構築します。
  • パスに従ってください。

  • まず、印刷の開始点を取得する方法を考え出すようにしてください。それはかなり簡単です。

  • ここまで進んだら、その値である開始点の近傍を印刷します。

  • 次に、各隣人に対して同じことを行います！

于 2013-02-05T18:47:25.053 に答える
0

次のコードはあなたが説明したことを実行すると思います。最初のノード（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も表示されます。

于 2013-02-05T18:37:14.537 に答える