PROBLEM STATEMENT
Pyrotex, Inc., has contracted you to develop a fire simulation program for
them. Given a two-dimensional map of a region, you must determine the length of
time for a fire to extinguish itself (by running out of fuel). In addition to
the map, you are given the coordinates of the starting location of the fire.
The String[] representing the map will be constructed as follows:
'.' represents grass. Grass, being fairly flammable, will burn if surrounded by
fire on at least one side. Once caught on fire, grass will burn for 3 minutes.
'T' represents trees. Trees will only burn if surrounded by fire on >= 3 sides.
Once on fire, trees will burn for 6 minutes.
'H' represents a house. Houses will burn if surrounded by fire on >= 4, and
will burn for 9 minutes.
'R' represents a rock. Rocks cannot burn, no matter how much fire is
surrounding them.
Note that grass, trees, and houses start burning the minute after the correct
conditions are met. For instance, if at minute 2, a house is surrounded by fire
on >= 4 sides, it will start burning at minute 3.
Note: Fire can spread on diagonals, as well as on the horizontal and vertical
axes.
Once a house or an area of grass or trees has been burnt, it cannot catch on
fire again.
Example of being "surrounded":
"..."
".HR"
"RTT"
The house in the middle is surrounded by 4 grass, 2 rocks, and 2 trees.
Create a class Fire containing a method burnTime, which takes a String[]
representing a map and a String[] representing the location of the fire.
burnTime returns the number of minutes until the fire is completely
extinguished.
DEFINITION
Class name: Fire
Method name: burnTime
Parameters: String[], String[]
Return type: int
Method signature (be sure your method is public):
int burnTime(String[] map, String[] coord)
The String[] representing the initial fire coordinates will be constructed as
follows:
Each coord String will be composed of an integer followed by a comma followed
by an integer, e.g.
"<x-coordinate>,<y-coordinate>"
So, "1,2" means column 1, row 2. (Note that quotes are included for clarity
only).
All coordinates are zero-based.
Each string will contain no spaces and exactly one comma. Also, each coordinate
will be within the appropriate range for the given map.
Grass, trees, and houses initially on fire will burn for 3, 6, and 9 minutes
respectively.
TopCoder will enforce the following restrictions:
* Each map String will contain between 1 and 20 characters, inclusive.
* There will be between 1 and 20 map Strings, inclusive.
* All map Strings will be the same length.
* Each map String will be composed of '.', 'T', 'R', and 'H' only
(case-sensitive).
* Each map String will be composed of '.', 'T', 'R', and 'H' only
(case-sensitive).
* There will be between 1 and 50 coord Strings, inclusive.
* Rocks will not be included in the coord Strings.
* Each coord String will be properly formatted, as described above. There will
be no spaces and exactly one comma.
* Each coord String "x,y" will contain integers that are valid coordinates for
the given map. (i.e., if the map is 10x15, the coordinates will be such that 0
<= x < 10, and 0 <= y < 15).
Let a number (1-9) show the amount of time something has left to burn, and let
'*' represent a completely burnt area.
So, if at time x, you have a map:
"321R"
"3TRR"
"RRR."
The tree at (1,1) is surrounded on four sides by fire, and thus is set ablaze
at time (x+1), so the next minute shows:
"21*R"
"26RR"
"RRR."
Since the 321 each expend one minute of burning time and become "21*" and the
"T" was surrounded and becomes a "6", since trees burn for 6 minutes total.
Example 1:
{"....."
".TTH."
"RTTR."
"....."},
{"1,0","0,1"}
Minute 0: (initial)
".3..."
"3TTH."
"RTTR."
"....."
Minute 1:
"323.."
"2TTH."
"RTTR."
"....."
Minute 2:
"2123."
"16TH."
"RTTR."
"....."
Minute 3:
"1*123"
"*56H3"
"RTTR."
"....."
Minute 4:
"***12"
"*4592"
"RTTR3"
"....."
Minute 5:
"****1"
"*3481"
"RT6R2"
"...33"
Minute 6:
"*****"
"*237*"
"R65R1"
".3322"
Minute 7:
"*****"
"*126*"
"R54R*"
"32211"
Minute 8:
"*****"
"**15*"
"R43R*"
"211**"
Minute 9:
"*****"
"***4*"
"R32R*"
"1****"
Minute 10:
"*****"
"***3*"
"R21R*"
"*****"
Minute 11:
"*****"
"***2*"
"R1*R*"
"*****"
Minute 12:
"*****"
"***1*"
"R**R*"
"*****"
Minute 13:
"*****"
"*****"
"R**R*"
"*****"
Thus, the method returns 13.
Example 2:
If the map is:
".TTTTTTTTTTTTHHHHH"
"...H...TTTTTH...HH"
".TTTTTTTTTTTR...R."
".TTTTTTTTTTRR....."
"...RRHTTHRHHHHHT.."
Coordinates are: "0,1","17,4"
Method returns: 27
Example 3:
Map:
"........."
"........."
"........."
"........."
"........."
"........."
"........."
"...RRR.R."
"..TT....."
"..TT....."
"..TT....."
"..TT....."
Coordinates: "2,1","1,8","5,8","3,8","5,3","2,11","2,9","0,4","6,8","4,1"
Method returns: 9