You are given a rectangular grid representing a city. Each cell contains one of the following characters:

• 'S': A source that emits a signal.
• 'B': A blocker that prevents signals from passing.
• '.': An empty cell through which signals can pass.
• 'T': A target that must receive a signal.

At time 0, every source begins emitting a signal. All signals propagate simultaneously by one cell per unit of time in the four cardinal directions: up, down, left, and right.

Signals may travel through empty cells and target cells, but they cannot enter or pass through blocker cells.

Return the minimum time required for every target to receive a signal. Each target is reached by its nearest source, so the required time is the greatest arrival time among all targets. Return -1 if at least one target cannot be reached.

Method

minimumSignalTime

int minimumSignalTime(List<String> grid)

Parameters

• grid: A list of equal-length strings representing the rows of the city grid.

Returns

Return the minimum time required for all targets to receive a signal. Return -1 if any target is unreachable.

Constraints

• 1 ≤ grid.size() ≤ 1,000
• 1 ≤ grid.get(0).length() ≤ 1,000
• Every string in grid has the same length.
• Every character is 'S', 'B', '.', or 'T'.
• The grid contains at least one source.
• The grid contains at least one target.
• Sources and targets may appear multiple times.
• Movement outside the grid is not allowed.

Follow-up

Suppose exactly one blocker may be changed into an empty cell. Determine which blocker should be removed to minimize the time required for all targets to receive a signal.

If multiple blockers produce the same minimum time, choose the blocker with the smaller row index. If their row indices are also equal, choose the one with the smaller column index.

Examples

Example 1

minimumSignalTime(grid = List.of("S.BT", "..B.", "T..S"))

Output: 2

The target in the first row is reached by the bottom-right source in 2 units of time. The target in the last row is reached by the top-left source in 2 units of time. Therefore, every target has received a signal after 2 units.

Example 2

minimumSignalTime(grid = List.of("SBT.", "BBBB", "T..S"))

Output: -1

The target in the last row can receive a signal, but the target in the first row is separated from every source by blockers. Therefore, not all targets are reachable.