Grid BFS (flood fill)

BFS on a 2D grid — the shortest-path workhorse behind maze solving and flood fill. Each walkable cell is a node; edges connect 4-neighbours. Shortest path by cell count is guaranteed.

time O(rows × cols)

space O(rows × cols)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

queue = [start]
dist[start] = 0
while queue:
  (r, c) = queue.popleft()
  for (dr, dc) in 4-neighbours:
    nr, nc = r+dr, c+dc
    if in bounds and walkable and not visited:
      dist[nr][nc] = dist[r][c] + 1
      queue.append((nr, nc))