Grid BFS / Multi-source BFS
The Intuition
Imagine pouring a bucket of water onto one cell of a tiled floor. The water spreads to the 4 adjacent tiles in one second. In the next second, those newly wet tiles spread water to their dry neighbors. Every second, the frontier expands outward by one tile in every direction. The water doesn't skip tiles, doesn't jump ahead, and always reaches closer tiles before farther ones. That uniform expansion is exactly what BFS does on a grid.
The queue is the wavefront of water. You start by adding your source cell. You process every cell at distance 0 (just the source), then every cell at distance 1 (its neighbors), then distance 2, and so on. Because a queue is first-in-first-out, cells discovered earlier get processed earlier. That's why BFS guarantees shortest paths in unweighted grids. The first time water reaches a cell IS the shortest path to that cell.
Multi-source BFS is just pouring water at multiple points simultaneously. Picture five rotten oranges on a grid. At minute zero, all five start spreading rot to their fresh neighbors. At minute one, each of those newly rotten oranges spreads further. You don't run five separate floods. You dump all five starting cells into the queue at distance 0 and let a single BFS expand them all. The flood from each source spreads at the same rate, so the first flood to reach any cell wins, and that's the nearest-source distance.
Finding shortest paths in unweighted grids, computing distances from multiple sources simultaneously, simulating spreading processes (fire, infection, rotting), or flood-fill operations that require level-order traversal.
Edges have different weights (use Dijkstra on grid), need to find all paths (use DFS), or grid is sparse (convert to adjacency list, use regular BFS).
Variations:
- Single-source BFS: One starting cell, find shortest path to a target cell.
- Multi-source BFS: Multiple starting cells enqueued together at distance 0; computes nearest-source distance for every cell.
- 0-1 BFS: Uses a deque with 0-weight edges pushed to front and 1-weight edges pushed to back, handling two-cost grids without Dijkstra.
- 8-directional BFS: Extends the directions array to include diagonals for problems that allow diagonal movement.
- Grid is a single cell (1x1), answer is trivially 0 or the cell value itself
- Start or target cell is blocked, making the path impossible
- Entire grid is open with no obstacles, resulting in a simple Manhattan distance path
- Grid dimensions are 1xN or Nx1, reducing the problem to a 1D search
- All cells are sources in multi-source BFS, so every distance is 0
- Disconnected regions that BFS cannot reach from any source
Key Points
- •Use a queue initialized with all source cells for multi-source BFS
- •Process cells level by level to track distance or time
- •Mark cells visited when enqueuing, not when dequeuing, to avoid duplicates
- •Use a directions array for clean 4-directional or 8-directional movement
- •Multi-source BFS finds shortest distance from any source simultaneously
Code Template
1 from collections import deque
2
3 def grid_bfs(grid):
4 """Single-source BFS on a 2D grid.
5 Returns shortest distance from top-left to bottom-right."""
6 rows, cols = len(grid), len(grid[0])
7 if grid[0][0] == 1 or grid[rows-1][cols-1] == 1:
8 return -1
9
10 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
11 queue = deque([(0, 0, 0)]) # (row, col, distance)
12 visited = set()
13 visited.add((0, 0))
14
15 while queue:
16 r, c, dist = queue.popleft()
17 if r == rows - 1 and c == cols - 1:
18 return dist
19 for dr, dc in directions:
20 nr, nc = r + dr, c + dc
21 if (0 <= nr < rows and 0 <= nc < cols
22 and (nr, nc) not in visited
23 and grid[nr][nc] == 0):
24 visited.add((nr, nc))
25 queue.append((nr, nc, dist + 1))
26
27 return -1
28
29 def multi_source_bfs(grid, sources):
30 """Multi-source BFS: finds shortest distance from
31 any source to every cell."""
32 rows, cols = len(grid), len(grid[0])
33 dist = [[-1] * cols for _ in range(rows)]
34 queue = deque()
35
36 for r, c in sources:
37 dist[r][c] = 0
38 queue.append((r, c))
39
40 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
41
42 while queue:
43 r, c = queue.popleft()
44 for dr, dc in directions:
45 nr, nc = r + dr, c + dc
46 if (0 <= nr < rows and 0 <= nc < cols
47 and dist[nr][nc] == -1):
48 dist[nr][nc] = dist[r][c] + 1
49 queue.append((nr, nc))
50
51 return distCommon Mistakes
- Marking visited on dequeue instead of enqueue, causing duplicate processing
- Forgetting to handle out-of-bounds checks before accessing the grid
- Not initializing all sources into the queue at once for multi-source BFS
- Using DFS instead of BFS when shortest path is required