Choose One Blocker Removal for the Fastest Grid Signals

Problem Statement

You are given an m x n grid representing a city layout with four types of cells:

• 'S': Signal sources that broadcast simultaneously at time t = 0.
• 'T': Target receivers that need to receive a signal.
• 'B': Blockers that prevent signal propagation.
• '.': Empty cells where signals can travel freely.

At each unit of time, a signal in an active cell propagates to its four adjacent cells (up, down, left, right), provided the neighbor is not out of bounds and is not a blocker ('B'). Once a cell receives a signal, it can propagate it further in subsequent time steps.

You are allowed to remove at most one blocker from the grid (turning it into an empty cell '.'). Your goal is to find the minimum time required for all targets to receive a signal, and identify which blocker (if any) should be removed.

Tie-breaking Rules:

1. Minimize the completion time (the time at which the last target receives a signal).
2. If the minimum completion time can be achieved without removing any blocker, choose to remove no blocker.
3. If removing a blocker is required to achieve the minimal time (or if no removal achieves a worse time), and multiple blocker removals yield the same minimal time, pick the blocker with the smallest row index r. If still tied, pick the one with the smallest column index c.

If it is impossible for all targets to receive a signal even after removing any single blocker, return (-1, (-1, -1)).

Function Signature

def fastest_signal_delivery(grid: list[list[str]]) -> tuple[int, tuple[int, int]]:
    pass

Input

• grid: A 2D list of characters representing the grid.

Output

• Returns a tuple (min_time, (r, c)) where:
  • min_time is the earliest time all targets receive a signal, or -1 if unreachable.
  • (r, c) is the 0-indexed coordinate of the removed blocker, or (-1, -1) if no blocker is removed (or if unreachable).

Constraints

• 1 <= m, n <= 30
• 1 <= m * n <= 900
• grid[i][j] is one of 'S', 'T', 'B', or '.'.
• There is at least one 'S' and at least one 'T' in grid.

Examples

Example 1

grid = [
    ["S", ".", "B", "T"],
    [".", "B", "B", "."],
    [".", ".", ".", "."]
]
# Output: (3, (0, 2))

Explanation: Without removing any blocker, the signal must detour around the blockers along the bottom row, reaching the target at (0, 3) at time t = 7. By removing the blocker at (0, 2), the path (0, 0) -> (0, 1) -> (0, 2) -> (0, 3) takes only 3 steps.

Example 2

grid = [
    ["S", ".", "T"],
    [".", ".", "."]
]
# Output: (2, (-1, -1))

Explanation: All targets receive signals at t = 2 without removing any blocker. Since no removal is needed to achieve the minimum possible time, return (-1, -1).