Tìm kiếm theo chiều sâu (DFS)

1Deque<Integer> stack = new ArrayDeque<>();  // Biên duyệt kiểu ngăn xếp (LIFO)2stack.push(start);  // Nạp ô xuất phát3while (!stack.isEmpty()) {  // Đến khi ngăn xếp rỗng4  int node = stack.pop();  // Lấy ô mới đẩy vào5  if (visited[node]) continue;  // Bỏ qua nếu đã thăm6  visited[node] = true;  // Đánh dấu ô đã thăm7  if (node == goal) return buildPath();  // Tới đích — truy vết đường8  for (int neighbor : neighbors(node))  // Duyệt các ô kề đi được9    if (!visited[neighbor]) { parent[neighbor] = node; stack.push(neighbor); }  // Lưu cha, đi sâu hơn10}11 12List<Integer> neighbors(int cell) {  // Các ô kề đi được13  int r = cell / COLS, c = cell % COLS;14  int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};15  List<Integer> out = new ArrayList<>();16  for (int[] d : dirs) {17    int nr = r + d[0], nc = c + d[1];18    if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;19    int nbr = nr * COLS + nc;20    if (!walls.contains(nbr)) out.add(nbr);21  }22  return out;23}24 25List<Integer> buildPath() {  // Lần theo cha từ đích26  List<Integer> path = new ArrayList<>();27  for (int at = goal; at != -1; at = parent[at]) path.add(at);28  Collections.reverse(path);29  return path;30}