Tìm kiếm theo chiều rộng (BFS)

1Queue<Integer> queue = new ArrayDeque<>();  // Hàng đợi các ô cần thăm2queue.add(start); visited[start] = true;  // Nạp ô xuất phát3while (!queue.isEmpty()) {  // Đến khi hàng đợi rỗng4  int node = queue.poll();  // Lấy ô vào sớm nhất5  if (node == goal) return buildPath();  // Tới đích — truy vết đường6  for (int neighbor : neighbors(node))  // Duyệt các ô kề đi được7    if (!visited[neighbor]) {  // Bỏ qua ô đã thăm8      visited[neighbor] = true; parent[neighbor] = node;  // Đánh dấu và lưu cha9      queue.add(neighbor);  // Xếp vào hàng chờ10    }11}12 13List<Integer> neighbors(int cell) {  // Các ô kề đi được14  int r = cell / COLS, c = cell % COLS;15  int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};16  List<Integer> out = new ArrayList<>();17  for (int[] d : dirs) {18    int nr = r + d[0], nc = c + d[1];19    if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;20    int nbr = nr * COLS + nc;21    if (!walls.contains(nbr)) out.add(nbr);22  }23  return out;24}25 26List<Integer> buildPath() {  // Lần theo cha từ đích27  List<Integer> path = new ArrayList<>();28  for (int at = goal; at != -1; at = parent[at]) path.add(at);29  Collections.reverse(path);30  return path;31}