DWITE '10 R3 #4 - Forest Fires

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 10 \times 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 will contain 5 lines, the time it takes for the fire to capture the entire forest. If some piece of the forest survives, output -1.

Sample Input

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

Sample Output

3
-1

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.