Determine escape path with blockers and spreading fire
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Quick Answer: This question evaluates graph traversal and grid-based pathfinding skills, including connectivity analysis, obstacle handling, and reasoning about time-dependent spreading processes.
Escape Path Part C: Maximum Waiting Time with Spreading Fire
Constraints
- 1 <= m, n <= 300
- Grid contains exactly one 'S' and one 'T'.
- Zero or more 'F' (fire source) cells.
- '#' cells block movement AND block fire spread (never burn).
- Rule: you may occupy a cell at arrival time t only if t < fire_time[cell] (arrive strictly before it burns).
Examples
Input: ([['S', '.', '.', 'T'], ['.', '.', '.', '.'], ['.', '.', '.', '.'], ['F', '.', '.', '.']],)
Expected Output: 2
Explanation: Fire starts at (3,0). fire_time[S]=3, so w<3. Walking right reaches T at (0,3) in 3 steps; the most constrained path cell forces w<=2, and w=2 is still safe, so the answer is 2.
Input: ([['S', '.', '.', '.', '.', 'T'], ['.', '.', '.', '.', '.', '.'], ['F', '.', '.', '.', '.', '.']],)
Expected Output: 1
Explanation: Fire at (2,0). S=(0,0) catches fire at time 2, so w<2. The constraining path cell limits the max safe wait to w=1.
Input: ([['S', '.', '.', '.', 'T'], ['F', '.', '.', '.', '.']],)
Expected Output: 0
Explanation: Fire at (1,0) reaches S=(0,0) at time 1, so w must be 0. You can still just barely walk to T arriving strictly before it burns, so the answer is 0.
Input: ([['S', '.', '.', 'T', 'F']],)
Expected Output: -1
Explanation: T is adjacent to the fire source, so T burns at time 1. The shortest path to T takes 3 minutes (arriving at time 3), which is not strictly before T burns. Impossible even at w=0, so return -1.
Input: ([['S', '#', 'T']],)
Expected Output: -1
Explanation: A blocker wall separates S from T; T is unreachable regardless of fire, so return -1.
Input: ([['S', '.', 'T']],)
Expected Output: 1000000000
Explanation: There is no fire in the grid, so you can wait arbitrarily long. Return the sentinel 10^9.
Input: ([['S', '.', '.'], ['#', '#', '.'], ['T', '.', '.']],)
Expected Output: 1000000000
Explanation: T is reachable around the '#' wall and there is no fire, so waiting is unbounded; return 10^9.
Hints
- First compute, for every cell, the earliest minute it catches fire using a multi-source BFS from all 'F' cells. Blocked cells '#' never burn.
- For a fixed wait w, a cell entered at time t is safe iff t < fire_time[cell]; waiting at S for w minutes requires w < fire_time[S]. Run a timed BFS from S where the arrival time at a cell is w + (BFS distance).
- Feasibility is monotonic: if you can escape after waiting w, you can also escape waiting any smaller amount (arriving earlier is always at least as safe). So binary-search the largest feasible w.
- If a large cap still lets you reach T (or there is no fire at all), waiting is effectively unbounded — return the sentinel 10^9. If you can't reach T even at w=0, return -1.
Escape Path Part A: Reachability from S to T
Constraints
- 1 <= m, n <= 300
- Grid contains exactly one 'S' and one 'T'.
- '#' cells cannot be entered.
- Movement is 4-directional only.
Examples
Input: ([['S', '.', '.'], ['#', '#', '.'], ['T', '.', '.']],)
Expected Output: True
Explanation: Go right across the top row, down the right column, then left along the bottom row to reach T.
Input: ([['S', '#', 'T']],)
Expected Output: False
Explanation: A blocker wall directly between S and T leaves no path.
Input: ([['S', '.', 'T']],)
Expected Output: True
Explanation: Walk straight right from S to T through the free cell.
Input: ([['S']],)
Expected Output: False
Explanation: Grid has no 'T' cell, so it is unreachable; return False.
Input: ([['S', '.', '.', '.'], ['#', '#', '#', '.'], ['T', '#', '.', '.'], ['.', '#', '.', '#']],)
Expected Output: False
Explanation: T's only open neighbor (3,0) connects solely back to T; the rest of the reachable region is walled off from T, so it is unreachable.
Input: ([['S', '#'], ['#', 'T']],)
Expected Output: False
Explanation: S is fully boxed in by blockers; no move is possible.
Hints
- Locate S and T, then run a standard BFS or DFS treating '#' as walls.
- Mark cells visited as you enqueue them to avoid revisiting and infinite loops.
- Return true as soon as you pop (or reach) the target cell.
Escape Path Part B: Reachability After Adding One Blocker
Constraints
- 1 <= m, n <= 300
- Grid contains exactly one 'S' and one 'T'.
- 0 <= r < m and 0 <= c < n.
- If the new blocker lands on S or T, return False.
Examples
Input: ([['S', '.', 'T']], 0, 1)
Expected Output: False
Explanation: The only path from S to T runs through (0,1), which is now blocked, so T is unreachable.
Input: ([['S', '.', '.'], ['.', '.', 'T']], 0, 1)
Expected Output: True
Explanation: Even with (0,1) blocked, you can go down then right: (0,0)->(1,0)->(1,1)->(1,2)=T.
Input: ([['S', '.', '.'], ['#', '.', '.'], ['T', '.', '.']], 1, 1)
Expected Output: True
Explanation: Blocking (1,1) still leaves the route across the top and down the right side, then back to T at (2,0).
Input: ([['S', '.', '.'], ['#', '#', '.'], ['T', '#', '.']], 0, 1)
Expected Output: False
Explanation: With (0,1) blocked, S=(0,0) has no open neighbor ((1,0) is '#'), so it is fully isolated.
Input: ([['S', 'T']], 0, 1)
Expected Output: False
Explanation: The new blocker lands on T itself, so the target is blocked; return False.
Input: ([['S', '.', 'T'], ['.', '.', '.']], 0, 0)
Expected Output: False
Explanation: The new blocker lands on S itself, so you cannot start; return False.
Hints
- Reuse the Part A BFS but treat the extra cell (r, c) as if it were a '#'.
- Handle the degenerate cases where (r, c) equals the S or T position by returning False up front.
- No need to re-mutate the grid — keep (r, c) in a set and skip it during neighbor expansion.