填死胡同

选一种语言就能看到代码

def dead_end_fill(start, goal, n):
    filled = [False] * n
    changed = True
    while changed:
        changed = False
        for cell in range(n):
            if filled[cell] or cell == start or cell == goal:
                continue
            ways = 0
            for d in range(4):
                other = neighbor(cell, d)
                if other >= 0 and not filled[other]:
                    ways += 1
            if ways == 1:
                filled[cell] = True
                changed = True
    at = start
    back = -1
    path = [start]
    while at != goal:
        for d in range(4):
            other = neighbor(at, d)
            if other < 0 or other == back or filled[other]:
                continue
            back = at
            at = other
            break
        path.append(at)
    return path

function deadEndFill(start, goal, n) {
  const filled = new Uint8Array(n);
  let changed = true;
  while (changed) {
    changed = false;
    for (let cell = 0; cell < n; cell++) {
      if (filled[cell] || cell === start || cell === goal) continue;
      let ways = 0;
      for (let d = 0; d < 4; d++) {
        const other = neighbor(cell, d);
        if (other >= 0 && filled[other] === 0) ways++;
      }
      if (ways !== 1) continue;
      filled[cell] = 1;
      changed = true;
    }
  }
  const path = [start];
  let at = start;
  let back = -1;
  while (at !== goal) {
    for (let d = 0; d < 4; d++) {
      const other = neighbor(at, d);
      if (other < 0 || other === back || filled[other] === 1) continue;
      back = at;
      at = other;
      break;
    }
    path.push(at);
  }
  return path;
}

int dead_end_fill(int start, int goal, int path[], int n) {
    char* filled = calloc(n, 1);
    int changed = 1;
    while (changed) {
        changed = 0;
        for (int cell = 0; cell < n; cell++) {
            if (filled[cell] || cell == start || cell == goal) continue;
            int ways = 0;
            for (int d = 0; d < 4; d++) {
                int other = neighbor(cell, d);
                if (other >= 0 && !filled[other]) ways++;
            }
            if (ways != 1) continue;
            filled[cell] = 1;
            changed = 1;
        }
    }
    int at = start;
    int back = -1;
    int count = 0;
    path[count++] = start;
    while (at != goal) {
        for (int d = 0; d < 4; d++) {
            int other = neighbor(at, d);
            if (other < 0 || other == back || filled[other]) continue;
            back = at;
            at = other;
            break;
        }
        path[count++] = at;
    }
    free(filled);
    return count;
}

std::vector<int> dead_end_fill(int start, int goal, int n) {
    std::vector<char> filled(n, 0);
    bool changed = true;
    while (changed) {
        changed = false;
        for (int cell = 0; cell < n; cell++) {
            if (filled[cell] || cell == start || cell == goal) continue;
            int ways = 0;
            for (int d = 0; d < 4; d++) {
                int other = neighbor(cell, d);
                if (other >= 0 && !filled[other]) ways++;
            }
            if (ways != 1) continue;
            filled[cell] = 1;
            changed = true;
        }
    }
    std::vector<int> path{start};
    int at = start;
    int back = -1;
    while (at != goal) {
        for (int d = 0; d < 4; d++) {
            int other = neighbor(at, d);
            if (other < 0 || other == back || filled[other]) continue;
            back = at;
            at = other;
            break;
        }
        path.push_back(at);
    }
    return path;
}

static List<int> DeadEndFill(int start, int goal, int n) {
    bool[] filled = new bool[n];
    bool changed = true;
    while (changed) {
        changed = false;
        for (int cell = 0; cell < n; cell++) {
            if (filled[cell] || cell == start || cell == goal) continue;
            int ways = 0;
            for (int d = 0; d < 4; d++) {
                int other = Neighbor(cell, d);
                if (other >= 0 && !filled[other]) ways++;
            }
            if (ways != 1) continue;
            filled[cell] = true;
            changed = true;
        }
    }
    var path = new List<int> { start };
    int at = start;
    int back = -1;
    while (at != goal) {
        for (int d = 0; d < 4; d++) {
            int other = Neighbor(at, d);
            if (other < 0 || other == back || filled[other]) continue;
            back = at;
            at = other;
            break;
        }
        path.Add(at);
    }
    return path;
}

static List<Integer> deadEndFill(int start, int goal, int n) {
    boolean[] filled = new boolean[n];
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int cell = 0; cell < n; cell++) {
            if (filled[cell] || cell == start || cell == goal) continue;
            int ways = 0;
            for (int d = 0; d < 4; d++) {
                int other = neighbor(cell, d);
                if (other >= 0 && !filled[other]) ways++;
            }
            if (ways != 1) continue;
            filled[cell] = true;
            changed = true;
        }
    }
    List<Integer> path = new ArrayList<>();
    path.add(start);
    int at = start;
    int back = -1;
    while (at != goal) {
        for (int d = 0; d < 4; d++) {
            int other = neighbor(at, d);
            if (other < 0 || other == back || filled[other]) continue;
            back = at;
            at = other;
            break;
        }
        path.add(at);
    }
    return path;
}