Depth-First Search

1Deque<Integer> stack = new ArrayDeque<>();  // Frontier as a stack (LIFO)2stack.push(start);  // Seed with the start cell3while (!stack.isEmpty()) {  // Until stack is empty4  int node = stack.pop();  // Take newest pushed cell5  if (visited[node]) continue;  // Skip if already visited6  visited[node] = true;  // Mark cell visited7  if (node == goal) return buildPath();  // Goal found — trace path8  for (int neighbor : neighbors(node))  // Scan passable neighbors9    if (!visited[neighbor]) { parent[neighbor] = node; stack.push(neighbor); }  // Record parent, go deeper10}11 12List<Integer> neighbors(int cell) {  // Passable 4-neighbors13  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() {  // Walk parent back from goal26  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}