Let me take you down, cause I'm going to strawberry fields
-John Lennon
Farmer John has a rectangular strawberry field that is w units wide by h units high. This means the territory is divided into w*h squares of equal size. Some of these squares have suddenly caught on fire, and farmer John has called the firemen in a desperate attempt to save his field. After each hour, all squares that are neighbors (horizontally, vertically or diagonally) of squares that are on fire will also be on fire.
..... ###.. ####. #####
.#... ###.. ####. #####
..... -> ###.. -> ####. -> #####
#.... ##... ####. #####
..... ##... ###.. #####
Here you can see the initial field with only 2 squares on fire, and the way the fire expands after each hour. After 3 hours, the entire field is covered with flames. If the firemen get to the place after 2 hours, 6 squares of field will be saved. If they get there after 1 hour, 12 squares will be saved, and if they get there instantly (after 0 hours) 23 squares will be saved.
Farmer John needs to know the maximum time the firemen can take to arrive in order to save at least need squares of the strawberry field.
You will be given w and h as two ints and need as a String representing an integer, all as explained above, and a String[] fire with a list of the squares that have caught on fire initially. Each element of fire will be formatted as "X Y" (quotes for clarity), where X and Y are integers between 1 and w and h, respectively, indicating the column and row of a square on fire. Return the maximum number of hours the firemen can take to allow John to save at least need units of his field.
|