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
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,
|
|
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...
|
|
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.... :)
|
|
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 |