FFIRE - Forest Fires

no tags 

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

hide comments
:D: 2012-08-07 12:18:36

Agreed. With higher constraints it could make for a very easy classical, but now any algo will pass. I wanted to give some more time for the author to make the constraints higher. Moving to tutorial.

Hussain Kara Fallah: 2012-08-07 07:43:31

Should be moved to tutorial :)

Sanchit Manchanda: 2012-07-05 06:20:55

i am getting wrong answer. id-7262290 can you tell me what i am doing wrong.. i tried this,

TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTFTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT

ans was 6..

also tried the given sample input in the problem, getting the right answer..!

EDIT- problem corrected.. i had a stupid constraint.. ans is 11 for this, and not 6...
but now i am getting TLE :(

EDIT AGAIN- Don't forget the case of -1, which would be
..........
..........
..........
...TT.TT..
...F......
..........
..........
..........
..........
..........

my code ran into infinite loop coz of this...! finally AC :D

Last edit: 2012-07-05 07:24:36
Aman Choudhary: 2012-06-26 18:36:37

key to this question is the case for -1 ...simple though :D

Rajesh Kumar: 2012-06-26 10:36:57

Print 0 if count of trees = 0...
caused me few WA..

Last edit: 2012-06-26 10:37:20
MR. BEAN : 2012-06-25 20:04:35

50th user to solve it :)

Kuba: 2012-06-25 19:06:39

Last edit: 2012-06-25 19:13:19
unXled: 2012-06-25 12:36:38

agreed with Amlesh....increasing the size doesnt change the difficulty but may be moving diagonal nd dn asking for max trees catch fire may change a prob a lil bit.... :)
got AC after a silly mistake.....

ayush: 2012-06-25 08:06:23

good for beginners ...

(Tjandra Satria Gunawan)(曾毅昆): 2012-06-23 17:39:07

My brute-force solution AC in 0.00s! ;)


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