Problem Statement
You are given a grid representing a city. Different types of entities are placed on the grid:
- Sources (marked
S): emit a signal - Blockers (marked
B): block signal propagation - Empty cells (marked
.): signal passes through freely - Targets (marked
T): need to be reached by a signal
A signal propagates from all sources simultaneously, one cell per unit of time, in 4 directions (up, down, left, right). Signals cannot pass through blockers.
Return the minimum time for all targets to receive a signal. If any target is unreachable, return -1.
Constraints
1 <= grid.length, grid[0].length <= 1000- Multiple sources and multiple targets
- At least one source exists
- Blockers create disconnected regions
Example
Input:
S . . B T
. . B . .
. . . . S
T . B . .
Output: 4
Explanation: Bottom-right source reaches the bottom-left target in 4 steps (going around the blockers). Top-right target is reached by top-left source in 3 steps (blocked direct path, goes around). Maximum of all target times = 4.
What the Interviewer Expects
- Identify multi-source BFS — start BFS from ALL source cells simultaneously (add all to queue at time 0).
- Handle blockers — skip cells marked as blockers during traversal.
- Track time — each BFS level = 1 time unit. Record when each target is first reached.
- Answer = max time across all targets — all targets must be reached, so the answer is the slowest one.
- Unreachable check — if any target is never visited after BFS completes, return -1.
- Problem comprehension is the real test — the scenario description is intentionally detailed. Extract the core algorithm from the noise.
Follow-ups
- What if signals weaken over distance and can only travel at most D cells? How does BFS change?
- What if some cells have different traversal costs (weighted grid)? Which algorithm replaces BFS?
- What if you can destroy one blocker — which blocker should you destroy to minimize total time?
- What if sources emit signals at different starting times? How do you modify the queue initialization?