深度优先

选一种语言就能看到代码

def depth_first(start, goal):
    prev = {start: -1}
    stack = [start]
    while stack:
        cell = stack.pop()
        if cell == goal:
            return path_to(prev, goal)
        for other in neighbors(cell):
            if other not in prev:
                prev[other] = cell
                stack.append(other)
    return []

function depthFirst(start, goal) {
  const prev = new Map([[start, -1]]);
  const stack = [start];
  while (stack.length > 0) {
    const cell = stack.pop();
    if (cell === goal) return pathTo(prev, goal);
    for (const other of neighbors(cell)) {
      if (prev.has(other)) continue;
      prev.set(other, cell);
      stack.push(other);
    }
  }
  return [];
}

int depth_first(int start, int goal, int prev[], int n) {
    int* stack = malloc(sizeof(int) * n);
    int top = 0;
    for (int i = 0; i < n; i++) prev[i] = -2;
    prev[start] = -1;
    stack[top++] = start;
    while (top > 0) {
        int cell = stack[--top];
        if (cell == goal) { free(stack); return 1; }
        for (int d = 0; d < 4; d++) {
            int other = neighbor(cell, d);
            if (other < 0 || prev[other] != -2) continue;
            prev[other] = cell;
            stack[top++] = other;
        }
    }
    free(stack);
    return 0;
}

std::vector<int> depth_first(int start, int goal) {
    std::unordered_map<int, int> prev{{start, -1}};
    std::vector<int> stack{start};
    while (!stack.empty()) {
        int cell = stack.back();
        stack.pop_back();
        if (cell == goal) return path_to(prev, goal);
        for (int other : neighbors(cell)) {
            if (prev.count(other) > 0) continue;
            prev[other] = cell;
            stack.push_back(other);
        }
    }
    return {};
}

static List<int> DepthFirst(int start, int goal) {
    var prev = new Dictionary<int, int> { [start] = -1 };
    var stack = new Stack<int>();
    stack.Push(start);
    while (stack.Count > 0) {
        int cell = stack.Pop();
        if (cell == goal) return PathTo(prev, goal);
        foreach (int other in Neighbors(cell)) {
            if (prev.ContainsKey(other)) continue;
            prev[other] = cell;
            stack.Push(other);
        }
    }
    return new List<int>();
}

static List<Integer> depthFirst(int start, int goal) {
    Map<Integer, Integer> prev = new HashMap<>();
    prev.put(start, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int cell = stack.pop();
        if (cell == goal) return pathTo(prev, goal);
        for (int other : neighbors(cell)) {
            if (prev.containsKey(other)) continue;
            prev.put(other, cell);
            stack.push(other);
        }
    }
    return List.of();
}