Optimal Commute: Nearest Transit Distance in a City Grid

Problem Statement

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

• 'T': A transit station.
• '.': An open road that commuters can walk through.
• 'X': An impassable building or obstacle.

Commuters can move in four cardinal directions (up, down, left, right) between adjacent open cells. Each step between adjacent cells takes 1 unit of distance. Commuters cannot move into or through 'X' cells.

Write a function to return an m x n matrix of integers where each cell contains the minimum distance to the nearest transit station 'T'. The rules for the output matrix are:

• The distance for a transit station 'T' is 0.
• The distance for an impassable cell 'X' is -1.
• If an open cell '.' cannot reach any transit station, its distance is -1.

Function Signature

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

Input & Output Format

• Input: A list of lists of strings grid of size m x n where each character is 'T', '.', or 'X'.
• Output: A 2D list of integers of size m x n representing the shortest distance to a transit station for each cell.

Constraints

• m == len(grid)
• n == len(grid[i])
• 1 <= m, n <= 500
• Total cells m * n <= 250,000
• grid[r][c] is one of 'T', '.', or 'X'.

Examples

Example 1

Input:
grid = [
  ['.', '.', 'T'],
  ['.', 'X', '.'],
  ['T', '.', '.']
]

Output:
[
  [2, 1, 0],
  [1, -1, 1],
  [0, 1, 2]
]

Explanation:

• (0, 2) and (2, 0) are transit stations, so their distances are 0.
• (1, 1) is an obstacle 'X', so its distance is -1.
• (0, 1) is 1 step from (0, 2), so its distance is 1.

Example 2

Input:
grid = [
  ['X', 'T'],
  ['.', 'X'],
  ['.', '.']
]

Output:
[
  [-1, 0],
  [-1, -1],
  [-1, -1]
]

Explanation: The open cells at (1, 0), (2, 0), and (2, 1) are blocked by 'X' and cannot reach the transit station at (0, 1), so their distance is -1.

Edge Cases

• No transit stations present in the grid (all reachable cells should return -1).
• Entire grid consists of transit stations or obstacles.
• 1 x 1 grid.