Determine escape path with blockers and spreading fire

You are given a 2D grid representing a grassland. - Each cell is one of: - `S`: start - `T`: target - `.`: free cell - `#`: blocked cell (cannot enter) - `F`: initial fire source (for Part C) - You can move 4-directionally (up/down/left/right) to adjacent cells. ### Part A: Reachability Given the grid with `#` blockers (no fire yet), determine whether there exists **any path** from `S` to `T`. ### Part B: After adding a blocker Now suppose one additional free cell is turned into a blocker `#` (you are given its coordinates). Determine whether `S` can still reach `T` after this change. ### Part C: Maximum waiting time with spreading fire Now consider fire spread in the grid: - At time `0`, all `F` cells are on fire. - Each minute, fire spreads from burning cells to their 4-directional neighbors that are not blockers `#`. - You start at `S`. You may **wait** at `S` for `w` minutes (where `w ≥ 0` is an integer), then start moving 1 cell per minute. - You cannot enter or stay in a cell that is on fire **at or before** the time you arrive. - Reaching `T` is allowed only if you arrive before it burns (state the rule explicitly in your solution, e.g., “arrive strictly before it burns”). Compute the **maximum** waiting time `w` such that you can still reach `T` safely. If it is impossible even with `w = 0`, return `-1`. If you can wait arbitrarily long (never blocked by fire), return a large sentinel value (e.g., `10^9`). ### Input/Output (for all parts) - Input: `grid` as an `m x n` array of characters; for Part B, also `(r, c)` coordinates to block. - Output: - Part A/B: boolean - Part C: integer maximum `w` ### Constraints (reasonable interview constraints) - `1 ≤ m, n ≤ 300` (or similar) - Grid contains exactly one `S` and one `T`. - Multiple `F` possible (Part C).