Minimum Hours to Cover Forest

You are given a rectangular grid representing a forest. Each cell in the grid is either a tree ('T') or an empty cell ('.'). Initially, some cells have the new type of tree marked by 'T'. Every hour, the trees spread to all adjacent cells — in all 8 directions (up, down, left, right, and the four diagonals) — if the cell is empty.

Your task is to determine the minimum number of hours required to cover all empty cells in the forest with trees. If there are no empty cells initially, the answer is 0.

The process can be mathematically described using a breadth-first search (BFS) where each cell is a vertex and there is an edge between any two cells that share a common side or touch at a corner. At each time step, all current tree cells propagate to their neighboring cells. The answer is the minimum number of iterations needed until no empty cell remains.

Formally, if we denote the grid as \(G\) with dimensions \(N \times M\), and the set of initial tree cells as \(S\), then the number of hours \(h\) is the minimum integer such that after \(h\) rounds of spreading, all cells \( (i,j) \) with \(G[i][j] = '.'\) have been visited.

inputFormat

The first line contains two integers \(N\) and \(M\) (1 \(\leq\) N, M \(\leq\) 1000) representing the number of rows and columns of the forest grid.

Each of the following \(N\) lines contains a string of length \(M\) consisting only of the characters 'T' and '.', which represent a tree and an empty cell, respectively.

outputFormat

Output a single integer: the minimum number of hours required for the new tree type to spread to cover all the empty cells in the forest.

4 5
T.T..
..T..
.....
.T..T

2