PROBLEM STATEMENT
You are playing a video game where you have to build a building on flat ground.
By moving the land up or down you can flatten the land so you can build the
building. Moving land up or down costs money and you would like to minimize
the amount of money you spend to place a building on the map.
The input is a map of the ground based on elevation. The first element of map
represents the northern most spots, and the first characters in each string
represent the western most spots. You would like to write a function that
given the map, the width and the length of the proposed building, returns the
minimum amount of money needed to spend to place the building. The width and
length are interchangeable, (i.e. is doesn't matter which direction either they
refer to north-south or east-west.)
The numbers on the map represent the elevations of the corners at that
position. So, the numbers at (0,0), (1,0), (1,1), and (0,1) represent the
elevations of the four corners of a single plot. In order to adjust the land
each corner will need to be moved up or down. To move a corner of a plot up
takes 2 dollars and to lower it one takes one dollar. So to raise an every
corner of a plot takes 8 dollars. Note that moving a corner of a plot up does
not affect the corners of adjacent plots. If one plot corner is moved up to
fit the building and the plots neighboring the corner are not at the same
level, a retaining wall is placed at no extra cost. So to move a corner down
one level for all of the four plots for which it is a corner, you need to buy 4
down operations.
DEFINITION
Class: BuildCost
Method: landCost
Parameters: String[], int, int
Returns: int
Method signature (be sure your method is public): int landCost(String[] map,
int width, int length);
NOTES
- In order for a building to be built ALL land under the base must be level and
inside the map.
- The building must be placed so it is aligned with the axes.
TopCoder will ensure the validity of all inputs. Inputs are valid if:
- map contains between 1 and 50 elements, inclusive.
- Each element of map contains between 1 and 50 characters, inclusive.
- Each element of map is the same length.
- Each element of map will contain only the characters '0'-'9'.
- length and width will be positive non-zero integers such that the building
can fit on the map in at least one way.
- The building must be aligned on the axes.
EXAMPLES
1)
map =
{"111111",
"112111",
"111111"}
width = 3
length= 2
It is easy to see that the building must span the north to south of the map
since it needs two plots. So we will look at the width:
If the northwest corner is at the 0,0 plot, 4 lowers will be needed to lower
the 4 corners that have elevation 2, to an elevation of 1.
If the northwest corner is at the 1,0 plot, 4 lowers are still needed.
If the northwest corner is at the 2,0 plot, only 2 lowers are needed because
the building is placed on the edge of the point at height 2.
Since that is all the options the minimum is 2 lowers, which is 2 dollars.
This case is seen here: ('-' and '|' are the edges of the plots, and the
numbers represent the height at the corners, 'X' represent where the building
is.}
Before:
1-1-1-1-1-1
| | | | | |
1-1-2-1-1-1
| | | | | |
1-1-1-1-1-1
After:
1-1-1-1-1-1
| | |X|X|X|
1-1-2-1-1-1
| | |X|X|X|
1-1-1-1-1-1
Since the 2 needs to be lowered twice under the building's left side the cost
is 2.
Returns 2
2)
{"111111",
"112111",
"111111"}
width = 2
length = 1
It is easy to find a plot that is 2 by 1 there are many plot that don't need
any raising or lowering.
Returns 0
3)
{"31",
"13"}
width = 1
length = 1
since it spans the entire map we need to find out how high the ground needs to
be.
At level 1 the two corners of elevation 3 need to be lowered 2 times so: 2*2*1
= 4 dollars
At level 2 the two corners of elevation 3 need to go down one and the two one
corners of elevation 1 need to go up by one, so: 2*1*1 + 2*1*2 = 6 dollars
At level 3 the two lowest corners need to go up by two, so: 2*2*2 = 8 dollars
Returns 4
4)
{"111111",
"112111",
"111111"}
width = 2
length = 3
This is the same as example 1, except the width and length are switched.
Return 2