Breadth-First Search

// graph: adjacency list, e.g. { A: ["B", "C"], B: ["A", "D"], ... }
function bfs(graph, start) {
  const dist = { [start]: 0 }; // also our "seen" set
  const parent = { [start]: null };
  const queue = [start];
  let head = 0; // index of the front: O(1) dequeue
  while (head < queue.length) {
    const node = queue[head++];
    for (const next of graph[node]) {
      if (next in dist) continue; // already seen
      dist[next] = dist[node] + 1;
      parent[next] = node;
      queue.push(next);
    }
  }
  return { dist, parent };
}
 
function pathTo(parent, goal) {
  if (!(goal in parent)) return null; // unreachable
  const path = [];
  for (let at = goal; at !== null; at = parent[at]) path.push(at);
  return path.reverse();
}
// pathTo(bfs(graph, "A").parent, "G") → ["A", "B", "D", "F", "G"]

from collections import deque
 
# graph: adjacency list, e.g. {"A": ["B", "C"], "B": ["A", "D"], ...}
def bfs(graph, start):
    dist = {start: 0}  # also our "seen" set
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt in dist:
                continue  # already seen
            dist[nxt] = dist[node] + 1
            parent[nxt] = node
            queue.append(nxt)
    return dist, parent
 
def path_to(parent, goal):
    if goal not in parent:
        return None  # unreachable
    path = []
    at = goal
    while at is not None:
        path.append(at)
        at = parent[at]
    return path[::-1]
# path_to(bfs(graph, "A")[1], "G") → ['A', 'B', 'D', 'F', 'G']

const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
 
// grid: array of strings, "#" is a wall. Start top-left, exit bottom-right.
function stepsToExit(grid) {
  const rows = grid.length, cols = grid[0].length;
  const dist = grid.map((row) => new Array(row.length).fill(-1));
  dist[0][0] = 0;
  const queue = [[0, 0]];
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    if (r === rows - 1 && c === cols - 1) return dist[r][c];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] === "#" || dist[nr][nc] !== -1) continue;
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return -1; // the exit cannot be reached
}
 
stepsToExit(["...#.", ".#...", ".#.#.", "...#."]); // 7

from collections import deque
 
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 
# grid: list of strings, "#" is a wall. Start top-left, exit bottom-right.
def steps_to_exit(grid):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    dist[0][0] = 0
    queue = deque([(0, 0)])
    while queue:
        r, c = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return dist[r][c]
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] == "#" or dist[nr][nc] != -1:
                continue
            dist[nr][nc] = dist[r][c] + 1
            queue.append((nr, nc))
    return -1  # the exit cannot be reached
 
steps_to_exit(["...#.", ".#...", ".#.#.", "...#."])  # 7