Time to Reach All Targets

You are given a rectangular grid grid as an array of strings, one string per row. Every cell is one of four characters:

• S: a source cell.
• T: a target cell.
• B: a blocked cell.
• .: an open cell.

At time 0, every source cell is marked. Each unit of time, every marked cell marks its 4-directionally adjacent cells (up, down, left, right, never diagonally) that are not blocked. Marking spreads from all sources at once, and it passes through open, source, and target cells alike; it never enters a blocked cell.

Return the earliest time at which every target cell is marked. If some target can never be marked, return -1. If the grid contains no target cells, return 0.

Examples

Example 1

Input: grid = ["S..BT", "..B..", "....S", "T.B.."]
Output: 3
Explanation: The source at row 2, column 4 reaches the target at row 0, column 4 after 2 steps (up, up). The source at row 0, column 0 reaches the target at row 3, column 0 after 3 steps (down, down, down). The later of the two is 3.

Example 2

Input: grid = ["S.B", "BBT"]
Output: -1
Explanation: Blocked cells cut the target off from the only source.

Example 3

Input: grid = ["S..", ".B."]
Output: 0
Explanation: There are no targets, so nothing needs to be reached.