templates · Graph traversal

Multi-source BFS

  • Many starting points spread at the same time: rotting oranges, fire, signals from many towers
  • "Distance from every cell to the nearest X"
  • Running one BFS per source would repeat the same work again and again

Multi-source BFS

the one rule

The invariant

The queue holds cells in rings: all sources at 0, then every cell at distance 1, then 2, and so on.

write it from memory

The template

javajava.util.*
/** Distance from every cell to its nearest 0 (all 0s start together). Example: 01 Matrix. */static int[][] nearestZero(int[][] grid) {    int rows = grid.length, cols = grid[0].length;    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};    int[][] dist = new int[rows][cols];    Deque<int[]> queue = new ArrayDeque<>();    for (int r = 0; r < rows; r++) {        for (int c = 0; c < cols; c++) {            if (grid[r][c] == 0) {                   // a source                dist[r][c] = 0;                queue.offer(new int[] {r, c});       // ALL sources go in first, at distance 0            } else {                dist[r][c] = -1;                     // not reached yet            }        }    }    while (!queue.isEmpty()) {        int[] cell = queue.poll();        for (int[] d : dirs) {            int nr = cell[0] + d[0], nc = cell[1] + d[1];            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;            if (dist[nr][nc] != -1) continue;        // already reached (or a source)            dist[nr][nc] = dist[cell[0]][cell[1]] + 1; // one ring further out            queue.offer(new int[] {nr, nc});        }    }    return dist;                                     // -1 left = no source can reach it}

The only change from plain BFS: push every source before the loop. It is as if one invisible start joins them all.

fill in the blanks — only these lines change per problem

  1. line 9What a source is: a 0, a rotten orange (2), a gate, or every border cell.
  2. line 13Which cells still need a distance. Walls stay as they are and are never entered.
  3. line 22Which neighbours to skip: already reached, walls, or empty cells for rotting oranges.
  4. line 27What to return: the grid of distances, the last ring number (minutes), or -1 if a cell stays unreached.

complexity

What it costs

time O(rows × cols)
One BFS for all sources together: each cell is pushed once and checks 4 neighbours.
space O(rows × cols)
The dist grid, and a queue that may start with every source in it.

watch out

Common bugs

  • Running a separate BFS from each source. That is O(sources × cells) and times out on big grids.
  • Pushing sources one at a time inside the loop, so the rings mix and distances come out too big.
  • For "minutes until all rot": forgetting to check for a fresh cell left at the end, which means the answer is -1.

use it

Practise it on

learn it properly