Find the Time for Grid Signals to Reach Every Target

Problem Statement

You are given an m x n 2D grid representing a city map. Each cell in the grid contains one of the following characters:

• 'S': A signal source that emits a signal starting at time 0.
• 'T': A target that needs to receive a signal.
• 'B': A blocker that completely obstructs signal propagation.
• '.': An empty cell that signals can freely pass through.

At time 0, all sources emit signals simultaneously. Every unit of time, a signal travels from its current cell to its four orthogonal neighbors (up, down, left, right), provided the neighbor is not out of bounds and is not a blocker ('B'). Targets and empty cells do not block signals; signals continue propagating through them.

Return the minimum time required for every target cell to receive a signal. If there are no targets in the grid, return 0. If any target cannot be reached by any signal source, return -1.

Function Signature

def min_time_to_reach_all_targets(grid: list[list[str]]) -> int:
    pass

Constraints

• m == len(grid)
• n == len(grid[i])
• 1 <= m, n <= 500
• grid[r][c] is one of 'S', 'T', 'B', or '.'.

Examples

Example 1

Input: grid = [
  ["S", ".", ".", "B"],
  [".", "B", ".", "T"],
  [".", "T", ".", "."]
]
Output: 4

Explanation:

• Target at (2, 1) is reached at time 3 via path (0,0) -> (1,0) -> (2,0) -> (2,1).
• Target at (1, 3) is reached at time 4 via path (0,0) -> (0,1) -> (0,2) -> (1,2) -> (1,3).
• All targets receive a signal by time max(3, 4) = 4.

Example 2

Input: grid = [
  ["S", "B", "T"],
  ["B", "B", "."],
  [".", ".", "T"]
]
Output: -1

Explanation: The target at (0, 2) is surrounded by blockers and the edge of the grid, so it can never be reached.

Example 3

Input: grid = [
  ["S", "."],
  [".", "."]
]
Output: 0

Explanation: There are no targets, so the required time is 0.