Forest fires are really dangerous, and can be started by even the smallest flame. Spreading from tree to tree, fires can engulf an entire forest in a matter of weeks. Given a map of a forest with locations of where a fire (or multiple fires) might have started, determine how long it would take the fire to consume the entire forest.
The input file DATA4.txt will contain 5 test cases, each a 10×10 map, followed by a line of 10 dashes for visual separation.
- . – blank space
- T – a tree
- F – a tree on fire
Fires only spread from existing fire to adjacent trees, in 4 directions (so not diagonally). It takes 1 unit of time for the fire to spread from one location to the next. The fire spreads in all 4 directions at the same time.
The output file OUT4.txt will contain 5 lines, each stating the time it takes for the fire to consume the entire forest. If some piece of the forest survives, output −1.
..........
..........
..........
..........
..TTTTT...
..F...F...
..........
..........
..........
..........
----------
..........
..........
..........
...TT.TT..
...F......
..........
..........
..........
..........
..........
----------
3
-1