Как закодировать Node-соседей в Grid?

Question

Я новичок в программировании, и как школьное задание мне нужно реализовать алгоритмы поиска BFS, DFS и A * в Java, чтобы искать заданную цель с заданной стартовой позиции в сетке заданного размера, 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

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

, а затем с помощью цикла присваивать значение всем узлам в arrayList от 1 до 64 (если размер сетки был 8x8).

НО как-то мне нужно добавить соседей каждого узла,если кто-нибудь может дать мне некоторые детали, я был бы очень признателен.

Answer 1

Скажем, ваши Node расположены в 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 метод создаст ArrayList<Node>

Намного проще обрабатывать сетку в двумерной структуре данных, будь то массив массивов или список-список. Если вы настаиваете на наличии 1-D списка, вместо nodes[r][c] вы вызываете вспомогательную функцию nodeAt(r, c):

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

Это стандартное преобразование из двумерного индексирования в одномерное (при условии мажорный порядок строк ).