FFIRE - Forest Fires

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.

Input

The input contains a 10×10 map (i.e. 10 lines each consisting of 10 characters), where each character in the map is one of the following:

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

Fires only spread from trees that are on fire to adjacent trees in one of four directions: North, South, East or West (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 (i.e. fires move outwards from the source).

Output

The output should contain the time it takes for the fire to capture the entire forest (i.e. the time it takes for every tree to catch fire). If some piece of the forest survives, output -1.

Example

Input:
..........
..........
..........
..........
..TTTTT...
..F...F...
..........
..........
..........
..........

Output:
3

Added by:Amlesh Jayakumar
Date:2012-06-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:DWITE Programming Contest 2010

hide comments
2012-06-22 23:32:00 :D
With 10x10 some sub-optimal solutions, like O((W*H)^2), will pass. So increasing limit to something like 200x200 makes sense.
2012-06-22 20:50:31 Amlesh Jayakumar
@Miguel- It isn't meant to be a challenging problem (though I do agree that increasing the size doesn't change the difficulty much).
2012-06-22 13:47:25 Miguel Oliveira
Why limit the problem to just 10x10 maps?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.