BFS on Grids, in depth: flat indexing, mark-on-enqueue, path reconstruction, multi-source BFS, islands, border floods, (cell, k) states and memory at scale

The grid as an implicit graph

Take a grid with R rows and C columns. A cell (r, c) is passable or blocked. With 4-directional movement its neighbours are up, down, left and right; with 8-directional movement, add the diagonals. Each move has cost 1. That graph is never built explicitly: neighbours are computed on the fly, and the only memory you need is a distance (or visited) array of size R*C and a queue.

Two encoding choices pay off immediately. First, keep moves in a direction table such as DIRS4 = ((1,0),(-1,0),(0,1),(0,-1)) rather than four copies of the bounds check, so switching to 8 directions or knight moves is a one-line change. Second, use a flat index i = r*C + c for the distance array and queue entries. A flat list of integers is far cheaper than a dictionary of tuples in Python and a HashSet<Point> in Java, and divmod(i, C) recovers the coordinates.

The invariant that makes BFS correct is that the queue holds cells in non-decreasing order of distance, with at most two distinct values present at any moment: d and d+1. So the first time a cell is discovered, the distance assigned to it is final.

The template, and three details that carry correctness

Here is the template, with a parent array so the path can be rebuilt:

from collections import deque

DIRS4 = ((1, 0), (-1, 0), (0, 1), (0, -1))

def shortest_path(grid, start, goal, dirs=DIRS4):
    R, C = len(grid), len(grid[0])
    (sr, sc), (gr, gc) = start, goal
    if grid[sr][sc] == '#' or grid[gr][gc] == '#':
        return -1, []
    dist = [-1] * (R * C)
    parent = [-1] * (R * C)
    s, g = sr * C + sc, gr * C + gc
    dist[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        if u == g:
            break                        # distance of g is final once it is dequeued
        r, c = divmod(u, C)
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':
                v = nr * C + nc
                if dist[v] == -1:         # mark on ENQUEUE, not on dequeue
                    dist[v] = dist[u] + 1
                    parent[v] = u
                    q.append(v)
    if dist[g] == -1:
        return -1, []
    path, v = [], g
    while v != -1:
        path.append(divmod(v, C))
        v = parent[v]
    return dist[g], path[::-1]

Three details carry the correctness. Mark on enqueue. If you mark a cell visited only when it is dequeued, the same cell can be enqueued by up to four neighbours before it is processed. Distances stay correct but the queue can grow several times larger and the run slows down sharply on open grids. Check bounds before indexing. In Python, grid[-1] silently reads the last row, so a missing 0 <= nr check creates wrap-around edges instead of an error. Use -1 for unvisited rather than 0, so the start cell's distance of 0 is not mistaken for unvisited.

You can stop as soon as the goal is enqueued, which saves one layer of work; stopping when it is dequeued, as above, is simpler to reason about. Either is correct because distances are final when assigned.

Worked example: a 5 by 5 maze

Run the template on this 5 by 5 grid, with S at (0,0), G at (4,4) and # for walls:

S..#.
##.#.
.....
.###.
...#G

BFS pops (0,0) at distance 0 and discovers only (0,1), because (1,0) is a wall. The frontier then crawls along the top row to (0,2), turns down through the single gap at (1,2), and reaches the open middle row at distance 4. From there it spreads in both directions at once: left to (2,0) at 6, right to (2,4) at 6. The right branch climbs to (0,4) at 8 and descends to G at 8. The left branch keeps going down and round the bottom-left, reaching (4,2) last at distance 10. Cell (4,3) is a wall, so the two branches never meet along the bottom row.

Following parent back from G yields (0,0) (0,1) (0,2) (1,2) (2,2) (2,3) (2,4) (3,4) (4,4), eight moves. If several shortest paths exist, which one you get depends on the order of DIRS4; if your output must be deterministic or must prefer, say, fewer turns, encode that in the direction order or in the state rather than hoping.

Multi-source BFS

Many grid questions ask for the distance from each cell to the nearest of several sources: minutes until every orange rots, distance from every room to the nearest gate, the time a fire takes to reach each cell. Running BFS from each source costs O(k*R*C). Multi-source BFS puts all sources in the queue at distance 0 before the loop starts, which is equivalent to adding a virtual super-source connected to each of them. One run, O(R*C) total.

def minutes_to_rot(grid):            # 2 = rotten, 1 = fresh, 0 = empty
    R, C = len(grid), len(grid[0])
    dist = [-1] * (R * C)
    q, fresh = deque(), 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                dist[r * C + c] = 0
                q.append(r * C + c)
            elif grid[r][c] == 1:
                fresh += 1
    last = 0
    while q:
        u = q.popleft()
        r, c = divmod(u, C)
        for dr, dc in DIRS4:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                v = nr * C + nc
                if dist[v] == -1:
                    dist[v] = last = dist[u] + 1
                    fresh -= 1
                    q.append(v)
    return last if fresh == 0 else -1

The answer is the largest distance assigned, and the count of unreached fresh cells detects the impossible case. The same structure computes a distance transform of a binary image, and a nearest-facility map in logistics. If you also need to know which source is nearest, carry a source label array alongside the distances; ties go to whichever source's wave got there first in queue order.

Regions: islands, labels and border floods

Counting islands, measuring blob areas and labelling connected components are traversal problems rather than shortest-path problems: you need reachability, not distance. Loop over every cell; when you find unvisited land, start a BFS from it, mark everything it reaches with a component id, and increment the count. Total cost is O(R*C) because every cell is enqueued once across all searches.

BFS and an iterative DFS give the same labels here. Avoid recursive DFS on large grids: a 1000 by 1000 all-land grid creates a recursion depth of up to a million and blows Python's default limit and most thread stacks. When cells arrive incrementally, such as land being added one cell at a time with a question after each addition, re-running BFS each time is quadratic; union-find handles that in near-constant time per update.

A useful inversion is the border flood. To find regions not connected to the edge, such as water enclosed by land or surrounded board regions, start a multi-source BFS from every passable border cell and mark what it reaches. Everything unmarked is enclosed. This replaces a per-region check of whether the edge is reachable with one linear pass.

When position is not enough: adding state

The template breaks the moment the future depends on more than your position. Classic cases: you may remove up to k walls; you collect keys that open doors; your momentum or facing direction matters. The fix is to search over states (r, c, extra) rather than cells, with a visited array of size R*C*E where E is the number of values extra can take.

def shortest_with_breaks(grid, k):
    R, C = len(grid), len(grid[0])
    K = k + 1
    seen = bytearray(R * C * K)              # (cell, walls broken so far)
    q = deque([(0, 0, 0)])                   # (cell index, breaks used, distance)
    seen[0] = 1
    while q:
        u, b, d = q.popleft()
        if u == R * C - 1:
            return d
        r, c = divmod(u, C)
        for dr, dc in DIRS4:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C:
                nb = b + (grid[nr][nc] == 1)  # 1 = wall
                if nb <= k:
                    s = (nr * C + nc) * K + nb
                    if not seen[s]:
                        seen[s] = 1
                        q.append((nr * C + nc, nb, d + 1))
    return -1

Reaching a cell with fewer breaks used is strictly better, so a common optimization keeps only the best b per cell, but the full state space is the safe default. For keys, extra is a bitmask of collected keys, giving 2^keys layers. The implicit-graph BFS guide covers state design in depth. When moves have two costs, such as free moves along a conveyor and cost-1 moves elsewhere, plain BFS gives wrong answers; use 0-1 BFS with a deque.

Large grids: memory and speed

On large grids, memory, not time, is usually the constraint. A 20,000 by 20,000 map has 400 million cells. A Python list of distances costs 8 bytes per slot for the pointer alone, about 3.2 GB; a bytearray visited mask costs 400 MB and a bitset 50 MB. In compiled languages, store distances in an int32 array (1.6 GB here) or, if you only need reachability or the path, a visited bitset plus a one-byte parent direction (0 to 3) instead of a full parent index. The queue holds at most about one frontier, which on an open grid is a diamond of perimeter O(R+C), but on a maze it can approach the cell count, so preallocate a ring buffer of R*C integers rather than relying on a growable deque.

For repeated queries on a static map, such as game agents routing to a few fixed targets, precompute a distance field per target once and answer each query by walking downhill in the field. For single long-distance queries on huge open maps, bidirectional BFS, A* with a Manhattan heuristic, or jump point search reduce the explored area dramatically, though each brings its own correctness conditions.

Failure modes

• Row and column swapped. Using grid[c][r] or r*R + c instead of r*C + c works on square test grids and fails on rectangular ones. Always test a 2 by 5 grid.
• Negative-index wrap. In Python, a missing lower-bound check lets grid[-1][c] connect the top row to the bottom.
• Mark on dequeue. Correct answers, inflated queue, time limits exceeded on open grids.
• Start or goal is a wall, or start equals goal: decide the answer explicitly instead of letting the loop return something accidental.
• Shared visited across layers of state. Marking the cell rather than (cell, state) makes a key-and-door search miss paths that revisit a cell with more keys.
• Diagonal corner cutting. With 8 directions, decide whether a diagonal move between two walls is legal; most maps forbid it, and the direction table alone does not.
• Using BFS with weights. Terrain costs need Dijkstra or 0-1 BFS; plain BFS returns the fewest moves, not the cheapest route.

What to do next

1. Write the template with a direction table, flat indices, mark-on-enqueue and a parent array; keep it as your reference implementation.
2. Test it on a rectangular grid, a grid with no path, start equal to goal, a blocked start, and an all-open 1000 by 1000 grid for speed.
3. Solve one problem of each family: shortest path in a maze, multi-source (rotting oranges), island counting, border flood (surrounded regions) and a state search (shortest path with k wall breaks).
4. Estimate memory before running on real maps: cells times bytes per cell for each array, and choose bitsets or narrow integers where you can.
5. When costs differ per move, switch to 0-1 BFS or Dijkstra; when the map is static and queried often, precompute distance fields.
6. Read the implicit-graph BFS guide next for richer states and bidirectional search.