特雷莫

选一种语言就能看到代码

def tremaux(start, goal):
    marks = {}
    seen = {start}
    cell = start
    path = [start]
    while cell != goal:
        pick = -1
        least = 2
        for d in range(4):
            if neighbor(cell, d) < 0:
                continue
            if marks.get(cell * 4 + d, 0) < least:
                least = marks.get(cell * 4 + d, 0)
                pick = d
        if pick < 0:
            return []
        other = neighbor(cell, pick)
        step = 2 if least == 0 and other in seen else 1
        marks[cell * 4 + pick] = least + step
        marks[other * 4 + (pick + 2) % 4] = least + step
        seen.add(other)
        path.append(other)
        if step == 1:
            cell = other
        else:
            path.append(cell)
    return path

function tremaux(start, goal) {
  const marks = new Map();
  const seen = new Set([start]);
  const path = [start];
  let cell = start;
  while (cell !== goal) {
    let pick = -1;
    let least = 2;
    for (let d = 0; d < 4; d++) {
      if (neighbor(cell, d) < 0) continue;
      const count = marks.get(cell * 4 + d) ?? 0;
      if (count >= least) continue;
      least = count;
      pick = d;
    }
    if (pick < 0) return [];
    const other = neighbor(cell, pick);
    const step = least === 0 && seen.has(other) ? 2 : 1;
    marks.set(cell * 4 + pick, least + step);
    marks.set(other * 4 + ((pick + 2) % 4), least + step);
    seen.add(other);
    path.push(other);
    if (step === 1) cell = other;
    else path.push(cell);
  }
  return path;
}

int tremaux(int start, int goal, int path[], int n) {
    char* marks = calloc(n * 4, 1);
    char* seen = calloc(n, 1);
    int cell = start;
    int count = 0;
    seen[start] = 1;
    path[count++] = start;
    while (cell != goal) {
        int pick = -1;
        int least = 2;
        for (int d = 0; d < 4; d++) {
            if (neighbor(cell, d) < 0) continue;
            if (marks[cell * 4 + d] >= least) continue;
            least = marks[cell * 4 + d];
            pick = d;
        }
        if (pick < 0) break;
        int other = neighbor(cell, pick);
        int step = (least == 0 && seen[other] == 1) ? 2 : 1;
        marks[cell * 4 + pick] = least + step;
        marks[other * 4 + (pick + 2) % 4] = least + step;
        seen[other] = 1;
        path[count++] = other;
        if (step == 1) cell = other;
        else path[count++] = cell;
    }
    free(marks);
    free(seen);
    return count;
}

std::vector<int> tremaux(int start, int goal, int n) {
    std::vector<int> marks(n * 4, 0);
    std::vector<char> seen(n, 0);
    std::vector<int> path{start};
    int cell = start;
    seen[start] = 1;
    while (cell != goal) {
        int pick = -1;
        int least = 2;
        for (int d = 0; d < 4; d++) {
            if (neighbor(cell, d) < 0) continue;
            if (marks[cell * 4 + d] >= least) continue;
            least = marks[cell * 4 + d];
            pick = d;
        }
        if (pick < 0) return {};
        int other = neighbor(cell, pick);
        int step = (least == 0 && seen[other] == 1) ? 2 : 1;
        marks[cell * 4 + pick] = least + step;
        marks[other * 4 + (pick + 2) % 4] = least + step;
        seen[other] = 1;
        path.push_back(other);
        if (step == 1) cell = other;
        else path.push_back(cell);
    }
    return path;
}

static List<int> Tremaux(int start, int goal, int n) {
    int[] marks = new int[n * 4];
    bool[] seen = new bool[n];
    var path = new List<int> { start };
    int cell = start;
    seen[start] = true;
    while (cell != goal) {
        int pick = -1;
        int least = 2;
        for (int d = 0; d < 4; d++) {
            if (Neighbor(cell, d) < 0) continue;
            if (marks[cell * 4 + d] >= least) continue;
            least = marks[cell * 4 + d];
            pick = d;
        }
        if (pick < 0) return new List<int>();
        int other = Neighbor(cell, pick);
        int step = least == 0 && seen[other] ? 2 : 1;
        marks[cell * 4 + pick] = least + step;
        marks[other * 4 + (pick + 2) % 4] = least + step;
        seen[other] = true;
        path.Add(other);
        if (step == 1) cell = other;
        else path.Add(cell);
    }
    return path;
}

static List<Integer> tremaux(int start, int goal, int n) {
    int[] marks = new int[n * 4];
    boolean[] seen = new boolean[n];
    List<Integer> path = new ArrayList<>();
    int cell = start;
    seen[start] = true;
    path.add(start);
    while (cell != goal) {
        int pick = -1;
        int least = 2;
        for (int d = 0; d < 4; d++) {
            if (neighbor(cell, d) < 0) continue;
            if (marks[cell * 4 + d] >= least) continue;
            least = marks[cell * 4 + d];
            pick = d;
        }
        if (pick < 0) return List.of();
        int other = neighbor(cell, pick);
        int step = least == 0 && seen[other] ? 2 : 1;
        marks[cell * 4 + pick] = least + step;
        marks[other * 4 + (pick + 2) % 4] = least + step;
        seen[other] = true;
        path.add(other);
        if (step == 1) cell = other;
        else path.add(cell);
    }
    return path;
}