演算法

1type Cell = [number, number];
2const WALL = 1, MUD = 2;
3const STEPS: Cell[] = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // right, down, left, up
4 
5function neighbours(grid: number[][], [r, c]: Cell): Cell[] {
6  return STEPS.map(([dr, dc]): Cell => [r + dr, c + dc]).filter(
7    ([nr, nc]) => grid[nr]?.[nc] !== undefined && grid[nr][nc] !== WALL,
8  );
9}
10 
11function walkBack(parent: Map<string, Cell | null>, goal: Cell): Cell[] {
12  const path: Cell[] = [];
13  for (let cell: Cell | null = goal; cell; cell = parent.get(String(cell))!) path.push(cell);
14  return path.reverse();
15}
16 
17function bfs(grid: number[][], start: Cell, goal: Cell) {
18  const parent = new Map<string, Cell | null>([[String(start), null]]);
19  const queue: Cell[] = [start];
20  for (let head = 0; head < queue.length; head++) {
21    const cell = queue[head];
22    if (String(cell) === String(goal)) {
23      return { path: walkBack(parent, goal), expanded: head + 1 };
24    }
25    for (const next of neighbours(grid, cell)) {
26      if (parent.has(String(next))) continue;
27      parent.set(String(next), cell);
28      queue.push(next);
29    }
30  }
31  return { path: [], expanded: queue.length };
32}
33 
34// Dijkstra when useEstimate is false, A* when it is true.
35function shortestPath(grid: number[][], start: Cell, goal: Cell, useEstimate: boolean) {
36  const estimate = ([r, c]: Cell) =>
37    useEstimate ? Math.abs(r - goal[0]) + Math.abs(c - goal[1]) : 0;
38  const best = new Map<string, number>([[String(start), 0]]);
39  const parent = new Map<string, Cell | null>([[String(start), null]]);
40  const done = new Set<string>();
41  const queue = new MinQueue();
42  let seq = 0;
43  queue.push([estimate(start), 0, seq++, ...start]);
44  while (queue.size > 0) {
45    const [, negG, , r, c] = queue.pop();
46    const cell: Cell = [r, c], g = -negG;
47    if (done.has(String(cell)) || g > best.get(String(cell))!) continue;
48    done.add(String(cell));
49    if (String(cell) === String(goal)) {
50      return { path: walkBack(parent, goal), cost: g, expanded: done.size };
51    }
52    for (const next of neighbours(grid, cell)) {
53      if (done.has(String(next))) continue;
54      const nextG = g + (grid[next[0]][next[1]] === MUD ? 5 : 1);
55      if (nextG >= (best.get(String(next)) ?? Infinity)) continue;
56      best.set(String(next), nextG);
57      parent.set(String(next), cell);
58      queue.push([nextG + estimate(next), -nextG, seq++, ...next]);
59    }
60  }
61  return { path: [], cost: Infinity, expanded: done.size };
62}
63 
64class MinQueue {
65  private a: number[][] = [];
66  get size() { return this.a.length; }
67  private less(x: number[], y: number[]) {
68    return (x[0] - y[0] || x[1] - y[1] || x[2] - y[2]) < 0;
69  }
70  push(entry: number[]) {
71    const a = this.a;
72    a.push(entry);
73    for (let i = a.length - 1, p = (i - 1) >> 1; i > 0 && this.less(a[i], a[p]); i = p, p = (i - 1) >> 1) {
74      [a[i], a[p]] = [a[p], a[i]];
75    }
76  }
77  pop(): number[] {
78    const a = this.a, top = a[0], last = a.pop()!;
79    if (a.length === 0) return top;
80    a[0] = last;
81    for (let i = 0; ; ) {
82      const l = 2 * i + 1, r = l + 1;
83      let m = i;
84      if (l < a.length && this.less(a[l], a[m])) m = l;
85      if (r < a.length && this.less(a[r], a[m])) m = r;
86      if (m === i) return top;
87      [a[i], a[m]] = [a[m], a[i]];
88      i = m;
89    }
90  }
91}