JAVA - 如何编码网格中的节点邻居？

Question

我是编程新手，作为一项学校任务，我需要在 Java 中实现 BFS、DFS 和 A* 搜索算法，以便从给定大小的网格中的给定起始位置搜索给定目标，4x4、8x8，等

首先，我不知道如何对所有节点的邻居进行编码。例如，在一个 8x8 的网格中，1 号瓷砖的邻居是 2 和 9，而 12 号瓷砖的邻居是 4、11、13 和 20，但我正在努力编写代码。我需要邻居部分，以便我可以通过水平或垂直移动通过​​邻居合法地从起始位置移动到网格的其他部分。

 1  2  3  4  5  6  7  8 
 9 10 11 12 13 14 15 16 
17 18 19 20 21 22 23 24 
25 26 27 28 29 30 31 32 
33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 
49 50 51 52 53 54 55 56 
57 58 59 60 61 62 63 64

我的节点类是:

class Node {
   int value;
   LinkedList<Node> neighbors;
   bool expanded;
}

假设我有一个 8x8 的网格，所以如果我以 8x8 的网格开始程序:

1 - 我的主要方法将为示例节点创建一个节点数组列表

ArrayList<Node> test = new ArrayList<Node>();

然后使用 for 循环为 arrayList 中的所有节点分配 1 到 64 之间的值(如果网格大小为 8x8)。

但不知何故我需要添加每个节点的邻居，如果有人能给我一些细节，我将非常感激。

Answer 1

假设您的 Node s 在 M 中列出行和 N列。为简单起见，令nodes[r][c]引用Node在行r和列 c (从零开始的索引)，当前为空 List<Node> neighbors我们想要构建的。

这是构建它们的一种方法:

for (int r = 0; r < M; r++) {
  for (int c = 0; c < N; c++) {
    Node n = nodes[r][c];
    List<Node> neighbors = n.neighbors;
    if (r > 0) {     // has north
      neighbors.add(nodes[r-1][c]);
    }
    if (r < M - 1) { // has south
      neighbors.add(nodes[r+1][c]);
    }
    if (c > 0) {     // has west
      neighbors.add(nodes[r][c-1]);
    }
    if (c < N - 1) { // has east
      neighbors.add(nodes[r][c+1]);
    }
  }
}

---

my main method will create an ArrayList<Node>

处理二维数据结构中的网格要容易得多，无论是数组的数组还是列表的列表。如果你坚持要有一个一维列表，那么用 nodes[r][c] 代替, 你调用 nodeAt(r, c)辅助函数:

Node nodeAt(int r, int c) {
   return nodesList.get(r * N + c);
}

这是从二维索引到一维索引的标准转换(假设 row-major order )。