StrawberryFieldsOnFire

SRM 322 · 2006-10-09 · by soul-net

SRM 322 · 2006-10-09 · by soul-net · Search

Show categories

Class Name: StrawberryFieldsOnFire

Return Type: int

Method Name: timeLimit

Arg Types: (int, int, string, vector<string>)

Problem Statement

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.

Notes

In the context of this problem, two squares are neighbors if they have at least one vertex in common. This means a square has a maximum of 8 neighbors.

Constraints

w and h will each be between 1 and 1000000000 (109), inclusive.
fire will contain between 1 and 50 elements, inclusive.
Each element of fire will be formatted "X Y", where X is an integer between 1 and w and Y is an integer between 1 and h, both inclusive, with no leading zeroes.
fire will contain no duplicates.
need will represent an integer without leading zeroes between 1 and w*h-N, inclusive, where N is the number of elements in fire.

Examples

5
5
"12"
{"1 4","2 2"}
Returns: 1

This is the example from the problem statement.

5
5
"1"
{"1 4","2 2"}
Returns: 2

The scenario is the same as before. In 3 hours everything is burned down, so to save at least 1 square, the maximum waiting time is 2.

5
5
"13"
{"1 4","2 2"}
Returns: 0

The same scenario again. To save more than 12, the firemen must be in place right away.

1000000000
1
"1"
{"1 1"}
Returns: 999999998

101
101
"400"
{"51 51"}
Returns: 49

With the fire starting right in the middle, you can save the entire perimeter by getting there 1 hour before the total burn out.

Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StrawberryFieldsOnFire with a public method int timeLimit(int w, int h, string need, vector<string> fire) · 109 test cases · 2 s / 256 MB per case