Grid BFS: Multi-source Distance Problems

Learning Outcome

Solve grid distance and spread problems by starting BFS from all sources at once.

Pattern Recognition

Item	Detail
Core signal	Many cells spread simultaneously or every cell needs distance to the nearest source.
Use when	Movement is unweighted and shortest distance/time is needed.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

A multi-source BFS is the same as adding a virtual source connected to every starting cell.

Exact Practice Question Names

Rotting Oranges
01 Matrix
As Far from Land as Possible
Shortest Bridge
Find the Safest Path in a Grid

Interview Approach

Push all source cells before BFS starts.
Mark visited when enqueuing.
Process by levels for time or distance.
For two-phase problems, first compute scores, then search on those scores.

Pseudocode

queue = all source cells
mark sources
steps = 0
while queue not empty:
  for each cell in current level:
    for each neighbor:
      if valid and unvisited: mark and push
  steps += 1

Sample Dry Run

In rotten oranges, all rotten cells start at minute 0. Every BFS layer rots adjacent fresh oranges together, giving minimum time.

Edge Cases

No source cells
No target cells
Boundary cells
Marking after pop creates duplicates

Common Mistakes

Running BFS from each source separately
Using DFS for shortest unweighted distance
Incrementing time after an empty final layer

Complexity

Item	Detail
Expected time	O(mn).
Expected space	O(mn) worst case queue/visited.

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.