## DWITE '10 R3 #4 - Forest Fires

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
##### DWITE Online Computer Programming Contest, December 2010, Problem 4

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 capture the entire forest.

The input will contain 5 test cases, each a map, followed by a line of dashes for visual separation.

• . - blank space
• T - a tree
• F - a tree on fire

Fires only spread from existing fire to adjacent trees, in directions (so not diagonally). It takes unit of time for the fire to spread from one location to the next. The fire spreads in all directions at the same time.

The output will contain 5 lines, the time it takes for the fire to capture the entire forest. If some piece of the forest survives, output .

#### Sample Input

..........
..........
..........
..........
..TTTTT...
..F...F...
..........
..........
..........
..........
----------
..........
..........
..........
...TT.TT..
...F......
..........
..........
..........
..........
..........
----------

#### Sample Output

3
-1

Problem Resource: DWITE