practice · medium · from Graphs

Shortest Path in a Maze (BFS)

time: O(rows · cols)
space: O(rows · cols)
tags: graphs · bfs · grid · shortest-path

in the wild Wavefront path planner on a robot's occupancy grid; warehouse-AGV routing; tile-based-game pathfinding (Pacman, Dwarf Fortress).

BFS · wavefront expansion

…

speed step 0 / 0

Problem

Given an m × n grid of 0s (free) and 1s (wall), a start (sr, sc), and a goal (gr, gc), return the length of the shortest path from start to goal moving only up / down / left / right through free cells. If unreachable, return -1. The path length is the number of cells visited minus one (= number of moves).

Examples

grid = [[0,0,0],
        [1,1,0],
        [0,0,0]]
start = (0, 0), goal = (2, 2)              → 4   (path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2))

grid = [[0,1],
        [1,0]]
start = (0, 0), goal = (1, 1)              → -1  (blocked)

start == goal                               → 0

Why this is the canonical "BFS on a grid" problem

The grid is a graph: free cells are nodes; adjacent free cells share an edge of weight 1. With all edges the same weight, the shortest path from start is found by BFS — not Dijkstra, not A*.

BFS expands cells layer by layer: it visits every cell at distance 1 before any cell at distance 2, then every cell at distance 2 before any cell at distance 3, and so on. The first time it reaches the goal, that distance is the answer.

The full procedure:

Queue starts with (start, distance = 0). Mark start as visited.
Pop the front. If it's the goal, return its distance.
Otherwise, for each of its 4 free unvisited neighbors, mark visited and enqueue with distance + 1.
If the queue empties, the goal is unreachable — return -1.

This is wavefront expansion — the foundational pathfinding algorithm in every robot occupancy-grid planner and every tile-based game. Master this, then graduate to Dijkstra (weighted edges) and A* (weighted + heuristic) — both keep the queue-based outer loop but change how cells are ordered.

Hints

Hint 1 — why BFS, not DFS?

DFS gives you some path, not the shortest. BFS visits cells in order of distance — once it reaches the goal, that distance is provably optimal.

Hint 2 — track the distance, not the path

You don't need to remember the path itself for this problem. Store (cell, distance) in the queue; when you pop a cell, you have its distance from start.

(If you do need the path, also store a parent[] map so you can reconstruct backwards from the goal.)

Hint 3 — mark visited when enqueuing, not when popping

A common bug: mark visited only when you pop a cell. That allows the same cell to be enqueued multiple times before it pops — blows up the queue with duplicates. Mark visited the moment you push it into the queue.

Solution

from collections import deque

def shortest_path(grid: list[list[int]], start: tuple[int, int], goal: tuple[int, int]) -> int:
    if not grid or not grid[0]:
        return -1
    m, n = len(grid), len(grid[0])
    sr, sc = start; gr, gc = goal
    if grid[sr][sc] == 1 or grid[gr][gc] == 1:
        return -1
    if start == goal:
        return 0

    visited = [[False] * n for _ in range(m)]
    visited[sr][sc] = True
    q: deque[tuple[int, int, int]] = deque([(sr, sc, 0)])
    while q:
        r, c, d = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:
                if (nr, nc) == goal:
                    return d + 1
                visited[nr][nc] = True              # mark on enqueue, not on pop
                q.append((nr, nc, d + 1))
    return -1

cases = [
    ([[0,0,0],[1,1,0],[0,0,0]],     (0, 0), (2, 2),  4),
    ([[0,1],[1,0]],                  (0, 0), (1, 1), -1),
    ([[0]],                           (0, 0), (0, 0),  0),
    ([[0,0,0,0]],                    (0, 0), (0, 3),  3),
]
for grid, s, g, expected in cases:
    got  = shortest_path(grid, s, g)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} shortest_path(.., {s}, {g}) = {got}  (expected {expected})")

function shortestPath(grid, start, goal) {
  if (!grid.length || !grid[0].length) return -1;
  const m = grid.length, n = grid[0].length;
  const [sr, sc] = start, [gr, gc] = goal;
  if (grid[sr][sc] === 1 || grid[gr][gc] === 1) return -1;
  if (sr === gr && sc === gc) return 0;

  const visited = Array.from({ length: m }, () => new Array(n).fill(false));
  visited[sr][sc] = true;
  const q   = [[sr, sc, 0]];
  let head  = 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (head < q.length) {
    const [r, c, d] = q[head++];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] === 0) {
        if (nr === gr && nc === gc) return d + 1;
        visited[nr][nc] = true;
        q.push([nr, nc, d + 1]);
      }
    }
  }
  return -1;
}

const cases = [
  [[[0,0,0],[1,1,0],[0,0,0]], [0, 0], [2, 2],  4],
  [[[0,1],[1,0]],              [0, 0], [1, 1], -1],
  [[[0]],                      [0, 0], [0, 0],  0],
  [[[0,0,0,0]],                [0, 0], [0, 3],  3],
];
for (const [grid, s, g, expected] of cases) {
  const got = shortestPath(grid, s, g);
  console.log(`${got === expected ? "✓" : "✗"} shortestPath(.., ${JSON.stringify(s)}, ${JSON.stringify(g)}) = ${got}  (expected ${expected})`);
}

use std::collections::VecDeque;

pub fn shortest_path(grid: &Vec<Vec<i32>>, start: (usize, usize), goal: (usize, usize)) -> i32 {
    if grid.is_empty() || grid[0].is_empty() { return -1; }
    let (m, n) = (grid.len(), grid[0].len());
    let ((sr, sc), (gr, gc)) = (start, goal);
    if grid[sr][sc] == 1 || grid[gr][gc] == 1 { return -1; }
    if start == goal { return 0; }

    let mut visited = vec![vec![false; n]; m];
    visited[sr][sc] = true;
    let mut q: VecDeque<(usize, usize, i32)> = VecDeque::new();
    q.push_back((sr, sc, 0));

    let dirs: [(isize, isize); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
    while let Some((r, c, d)) = q.pop_front() {
        for (dr, dc) in dirs {
            let nr = r as isize + dr;
            let nc = c as isize + dc;
            if nr < 0 || nr >= m as isize || nc < 0 || nc >= n as isize { continue; }
            let (nr, nc) = (nr as usize, nc as usize);
            if visited[nr][nc] || grid[nr][nc] == 1 { continue; }
            if (nr, nc) == goal { return d + 1; }
            visited[nr][nc] = true;
            q.push_back((nr, nc, d + 1));
        }
    }
    -1
}

fn main() {
    let cases: Vec<(Vec<Vec<i32>>, (usize, usize), (usize, usize), i32)> = vec![
        (vec![vec![0,0,0], vec![1,1,0], vec![0,0,0]], (0, 0), (2, 2),  4),
        (vec![vec![0,1], vec![1,0]],                   (0, 0), (1, 1), -1),
        (vec![vec![0]],                                 (0, 0), (0, 0),  0),
        (vec![vec![0,0,0,0]],                          (0, 0), (0, 3),  3),
    ];
    for (grid, s, g, expected) in cases {
        let got  = shortest_path(&grid, s, g);
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} shortest_path(.., {:?}, {:?}) = {}  (expected {})", s, g, got, expected);
    }
}

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

int shortest_path(std::vector<std::vector<int>>& grid,
                  std::pair<int, int> start,
                  std::pair<int, int> goal)
{
    if (grid.empty() || grid[0].empty()) return -1;
    int m = (int)grid.size(), n = (int)grid[0].size();
    auto [sr, sc] = start; auto [gr, gc] = goal;
    if (grid[sr][sc] == 1 || grid[gr][gc] == 1) return -1;
    if (start == goal) return 0;

    std::vector<std::vector<char>> visited(m, std::vector<char>(n, 0));
    visited[sr][sc] = 1;
    std::queue<std::tuple<int, int, int>> q;
    q.emplace(sr, sc, 0);

    int dirs[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    while (!q.empty()) {
        auto [r, c, d] = q.front(); q.pop();
        for (auto& [dr, dc] : dirs) {
            int nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (visited[nr][nc] || grid[nr][nc] == 1) continue;
            if (nr == gr && nc == gc) return d + 1;
            visited[nr][nc] = 1;
            q.emplace(nr, nc, d + 1);
        }
    }
    return -1;
}

int main() {
    struct Case { std::vector<std::vector<int>> grid; std::pair<int,int> s, g; int expected; };
    std::vector<Case> cases = {
        { {{0,0,0},{1,1,0},{0,0,0}}, {0,0}, {2,2},  4 },
        { {{0,1},{1,0}},              {0,0}, {1,1}, -1 },
        { {{0}},                      {0,0}, {0,0},  0 },
        { {{0,0,0,0}},                {0,0}, {0,3},  3 },
    };
    for (auto& c : cases) {
        int got = shortest_path(c.grid, c.s, c.g);
        std::cout << (got == c.expected ? "✓" : "✗")
                  << " shortest_path(.., (" << c.s.first << "," << c.s.second
                  << "), (" << c.g.first << "," << c.g.second << ")) = " << got
                  << "  (expected " << c.expected << ")\n";
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int shortest_path(int** grid, int m, int n, int sr, int sc, int gr, int gc) {
    if (grid[sr][sc] == 1 || grid[gr][gc] == 1) return -1;
    if (sr == gr && sc == gc) return 0;

    char* visited = calloc(m * n, sizeof(char));
    visited[sr * n + sc] = 1;
    // Queue of (r, c, d) flattened.
    int* q   = malloc(m * n * 3 * sizeof(int));
    int  hd  = 0, tl = 0;
    q[tl++] = sr; q[tl++] = sc; q[tl++] = 0;

    static const int dr[] = {1, -1, 0, 0};
    static const int dc[] = {0, 0, 1, -1};

    int ans = -1;
    while (hd < tl) {
        int r = q[hd++], c = q[hd++], d = q[hd++];
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (visited[nr * n + nc] || grid[nr][nc] == 1) continue;
            if (nr == gr && nc == gc) { ans = d + 1; goto done; }
            visited[nr * n + nc] = 1;
            q[tl++] = nr; q[tl++] = nc; q[tl++] = d + 1;
        }
    }
done:
    free(visited); free(q);
    return ans;
}

static int** mkgrid(int* flat, int m, int n) {
    int** g = malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        g[i] = malloc(n * sizeof(int));
        memcpy(g[i], flat + i * n, n * sizeof(int));
    }
    return g;
}
static void freegrid(int** g, int m) { for (int i = 0; i < m; i++) free(g[i]); free(g); }

int main(void) {
    int g1[] = {0,0,0,  1,1,0,  0,0,0};
    int**  G = mkgrid(g1, 3, 3);
    printf("%s shortest_path(g1) = %d  (expected 4)\n",
           shortest_path(G, 3, 3, 0, 0, 2, 2) == 4 ? "✓" : "✗",
           shortest_path(G, 3, 3, 0, 0, 2, 2));
    freegrid(G, 3);

    int g2[] = {0,1,  1,0};
    G = mkgrid(g2, 2, 2);
    printf("%s shortest_path(g2) = %d  (expected -1)\n",
           shortest_path(G, 2, 2, 0, 0, 1, 1) == -1 ? "✓" : "✗",
           shortest_path(G, 2, 2, 0, 0, 1, 1));
    freegrid(G, 2);

    int g3[] = {0};
    G = mkgrid(g3, 1, 1);
    printf("%s shortest_path(g3) = %d  (expected 0)\n",
           shortest_path(G, 1, 1, 0, 0, 0, 0) == 0 ? "✓" : "✗",
           shortest_path(G, 1, 1, 0, 0, 0, 0));
    freegrid(G, 1);
    return 0;
}

idle

The "mark visited when enqueuing, not when popping" detail is the difference between an O(m·n) BFS and one that pathologically re-enqueues the same cells over and over. Every robotics / game engine wavefront planner has this discipline baked in.

Complexity

Time: O(m · n) — each cell is enqueued at most once.
Space: O(m · n) for the visited grid and (in the worst case) the queue.
Weighted edges?: Plain BFS only works because every edge costs the same. With variable edge costs (different terrain), switch to Dijkstra (priority queue replacing the FIFO).
Goal-directed search?: If you can give a lower-bound estimate of the remaining distance (e.g. Manhattan to goal), upgrade to A* — same worst case, often much faster in practice.

In the wild

Robot occupancy-grid planners. Every ROS nav_core planner starts here: BFS or its grown-up siblings (A*, Theta*, Jump Point Search) over the costmap.
Warehouse AGV routing. Amazon Kiva / Locus robots compute paths over a discretized warehouse floor in essentially this way.
Tile-based games. Pacman, Dwarf Fortress, Stardew Valley — every grid-based enemy AI does some flavor of BFS / A*.
Maze-solving in puzzle apps, network-topology shortest-path on unweighted graphs, link-distance in social graphs.

Variations

Reconstruct the path itself. Add parent[][] storing the cell each cell was reached from; walk backwards from goal.
Weighted grid (terrain costs). Switch FIFO → min-priority-queue → Dijkstra.
A with heuristic.* Add a heuristic (Manhattan or Euclidean distance to goal) to the priority-queue key.
0-1 BFS. When edges weigh 0 or 1 (e.g. moving through walls costs 0 if you have a key), a deque-based BFS gives O(V + E).
Bidirectional BFS. Expand from start and goal simultaneously; meet in the middle. Often √n faster.
Multi-source BFS. Push every "source" into the queue at distance 0 — answers "shortest distance from any source" in one pass.