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).