A forest is a grid of R rows and C columns. Each cell is one of: F (already burning at minute 0), T (an unburnt tree), or . (bare ground). Every minute, fire spreads from each burning cell to any tree in a directly adjacent cell (up, down, left, right); that tree begins burning. Fire never spreads onto or through bare ground.
Report the number of minutes until every tree is burning. If some tree can never catch fire, report -1. If there are no trees at all, report 0.
Line 1: two integers R and C.
Next R lines: a string of exactly C characters, each F, T, or ..
A single integer: the minutes until all trees burn, -1 if impossible, or 0 if there are no trees.
F, T, or ..Example 1
Input
2 2 FT TT
Expected
2
Explanation
Minute 1 burns (0,1) and (1,0); minute 2 burns (1,1). All trees burn at minute 2.
Example 2
Input
2 3 FT. ..T
Expected
-1
Explanation
The tree at (1,2) is surrounded by ground and one already-checked cell; fire can never reach it, so the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →