재귀 백트래킹

언어를 고르면 코드가 열린다

def recursive_backtracker(w, h, rng):
    links = [0] * (w * h)
    seen = [False] * (w * h)
    stack = [0]
    seen[0] = True
    while stack:
        room = stack[-1]
        open_dirs = [d for d in range(4)
                     if neighbor(room, d) >= 0 and not seen[neighbor(room, d)]]
        if not open_dirs:
            stack.pop()
            continue
        d = rng.choice(open_dirs)
        other = neighbor(room, d)
        carve(links, room, other, d)
        seen[other] = True
        stack.append(other)
    return links

function recursiveBacktracker(w, h, rng) {
  const links = new Array(w * h).fill(0);
  const seen = new Array(w * h).fill(false);
  const stack = [0];
  seen[0] = true;
  while (stack.length > 0) {
    const room = stack[stack.length - 1];
    const openDirs = [];
    for (let d = 0; d < 4; d++) {
      const other = neighbor(room, d);
      if (other >= 0 && !seen[other]) openDirs.push(d);
    }
    if (openDirs.length === 0) {
      stack.pop();
      continue;
    }
    const d = openDirs[rng.below(openDirs.length)];
    const other = neighbor(room, d);
    carve(links, room, other, d);
    seen[other] = true;
    stack.push(other);
  }
  return links;
}

void recursive_backtracker(int links[], int w, int h) {
    int n = w * h;
    char* seen = calloc(n, 1);
    int* stack = malloc(sizeof(int) * n);
    int top = 0;
    stack[top++] = 0;
    seen[0] = 1;
    while (top > 0) {
        int room = stack[top - 1];
        int open_dirs[4];
        int count = 0;
        for (int d = 0; d < 4; d++) {
            int other = neighbor(room, d);
            if (other >= 0 && !seen[other]) open_dirs[count++] = d;
        }
        if (count == 0) {
            top--;
            continue;
        }
        int d = open_dirs[rand() % count];
        int other = neighbor(room, d);
        carve(links, room, other, d);
        seen[other] = 1;
        stack[top++] = other;
    }
    free(seen);
    free(stack);
}

void recursive_backtracker(std::vector<int>& links, int w, int h,
                           std::mt19937& rng) {
    std::vector<char> seen(w * h, 0);
    std::vector<int> stack{0};
    seen[0] = 1;
    while (!stack.empty()) {
        int room = stack.back();
        std::vector<int> open_dirs;
        for (int d = 0; d < 4; d++) {
            int other = neighbor(room, d);
            if (other >= 0 && !seen[other]) open_dirs.push_back(d);
        }
        if (open_dirs.empty()) {
            stack.pop_back();
            continue;
        }
        std::uniform_int_distribution<size_t> pick(0, open_dirs.size() - 1);
        int d = open_dirs[pick(rng)];
        int other = neighbor(room, d);
        carve(links, room, other, d);
        seen[other] = 1;
        stack.push_back(other);
    }
}

static int[] RecursiveBacktracker(int w, int h, Random rng) {
    int[] links = new int[w * h];
    bool[] seen = new bool[w * h];
    var stack = new Stack<int>();
    stack.Push(0);
    seen[0] = true;
    while (stack.Count > 0) {
        int room = stack.Peek();
        var openDirs = new List<int>();
        for (int d = 0; d < 4; d++) {
            int other = Neighbor(room, d);
            if (other >= 0 && !seen[other]) openDirs.Add(d);
        }
        if (openDirs.Count == 0) {
            stack.Pop();
            continue;
        }
        int dir = openDirs[rng.Next(openDirs.Count)];
        int next = Neighbor(room, dir);
        Carve(links, room, next, dir);
        seen[next] = true;
        stack.Push(next);
    }
    return links;
}

static int[] recursiveBacktracker(int w, int h, Random rng) {
    int[] links = new int[w * h];
    boolean[] seen = new boolean[w * h];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    seen[0] = true;
    while (!stack.isEmpty()) {
        int room = stack.peek();
        List<Integer> openDirs = new ArrayList<>();
        for (int d = 0; d < 4; d++) {
            int other = neighbor(room, d);
            if (other >= 0 && !seen[other]) openDirs.add(d);
        }
        if (openDirs.isEmpty()) {
            stack.pop();
            continue;
        }
        int dir = openDirs.get(rng.nextInt(openDirs.size()));
        int next = neighbor(room, dir);
        carve(links, room, next, dir);
        seen[next] = true;
        stack.push(next);
    }
    return links;
}