PROBLEM STATEMENT:
(For added clarity, Figures 1 through 4 are refered to throughout the problem
statement. The Figures can be located at
http://www.topcoder.com/contest/structure.html.)
The packers at ABC Chemical company have a problem. Given an irregularly shaped
3-d container, already filled with an incompressible fluid of negligible
density, they would like to know the minimum number of filling holes necessary
to completely fill the container with a new, incompressible fluid (with a
greater density). Each filling hole must be in the top of the container (as
opposed to the side), and each filling hole has a corresponding "escape" hole
for the existing fluid to come out of, with identical coordinates. (See Figure
1 for added clarity).
For the purposes of this problem, let "cell" define a columnar section
specified by a pair of x and y coordinates. That is, a cell at coordinates
(1,0) represents all volume with x coordinate 1, y coordinate 0, and z
coordinates of between 0 and 100, inclusive.
Your job is to determine the minimum number of filling holes necessary to
entirely fill the container. If you have an isolated area higher than the
surrounding area, the existing fluid cannot be pushed out, because it can only
go up (since it is less dense than the injected fluid), but is blocked by the
top of the container. But, if there is an adjoining cell with a higher
"ceiling", the less dense fluid can flow upwards to it, provided there is an
exit hole somewhere on the way up, see Figure 2. See Figure 3 for an example
where there is no exit hole on the way up.
The fluid being injected fills the container evenly, unless it cannot (as
explained above), and then may have a higher volume in one cell than another.
(See Figure 2 and Figure 3 for added clarity).
Implement a class Structure that contains a method maxFill. maxFill takes two
String[] representing the bottom and top surfaces of this structure and returns
the minimum number of holes that need to be created in the top of this
structure in order to fill it completely.
DEFINITION
Class: Structure
Method: maxFill
Parameters: String[], String[]
Returns: int
The method signature is:
int maxFill(String [] bottom, String[] top);
Be sure your method is public.
Each String in bottom and top will be formatted as space-delimited integers
representing the height boundary of this structure at that cell. There may be
more than one space between the numbers. Consider the following example:
bottom = {"1 1 2",
"1 0 0"}
top = {"3 2 3",
"1 5 7"}
For the purposes of this problem, assume all x and y coordinates are
zero-indexed. i.e., the first column has index 0, and the first row has index 0.
In this case, both bottom and top have dimensions 3X2. Let (1,0) represent the
cell in column 1, row 0. If we are looking at this structure from overhead, the
cell at (1,0) contains no space, since the height of the bottom surface equals
the height of the top. The cell at (1,1) has a space of 5 cubic units that
needs to be filled, since the height of the bottom surface at that point is 0
and the top surface 5.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
* Both bottom and top will contain the same number of elements, and each will
be of size 1 to 10, inclusive.
* All strings in bottom and top will contain between 1 and 10 integers,
inclusive, and all will have an equal number of integers.
* Each integer will be between 0 and 100, inclusive.
* In each pair of corresponding integers (i.e. for each cell, from an overhead
view), the height of the bottom will be less than or equal to height of the top.
NOTES
* Fluids cannot flow on diagonals, only on the horizontal and vertical. (See
Figure 4 for added clarity).
EXAMPLES
{"0 0",
"0 0"},
{"2 2",
"2 2"} represents a 2x2x2 cube. Creating one hole anywhere in the top surface
will fill the cube completely, so your method should return 1.
{"0 0 0",
"0 0 0",
"0 0 0"},
{"1 1 1",
"2 2 2",
"3 3 3"} represents a sort of stair-step structure. Creating one hole anywhere
in row 2 (where the height equals 3) will fill the entire structure, so the
method should again return 1.
For the following ascii images, let "Level x" denote the level between (height
x-1) and (height x).
For instance, "Level 1" is the level of cubes (1x1x1 unit volumes) between
height 0 and height 1.
For a more complicated structure, like:
{"0 0 1 1",
"0 0 1 2",
"3 0 3 3",
"3 0 4 4"}
{"2 3 2 5",
"0 0 2 5",
"5 0 5 5",
"5 0 5 5"},
we have cross sections, which, starting at the bottom, look like:
Note that -'s are not part of the structure, *'s are existing fluid, and +'s
are new fluid.
Level 1 Level 2 Level 3 Level 4 Level 5
* * - - * * * * - * - * - - - * - - - *
- - - - - - * - - - - * - - - * - - - *
- - - - - - - - - - - - * - * * * - * *
- - - - - - - - - - - - * - - - * - * *
Now, to fill this structure, we can start at (3,3) row 3, column 3, and inject
as much as we can.
After the fluid has flowed one unit outward, we have:
Level 1 Level 2 Level 3 Level 4 Level 5
* * - - * * * * - * - * - - - * - - - *
- - - - - - * - - - - * - - - * - - - *
- - - - - - - - - - - - * - * * * - + +
- - - - - - - - - - - - * - - - * - + +
After it has flowed another unit outward (and downward), we have:
Level 1 Level 2 Level 3 Level 4 Level 5
* * - - * * * * - * - * - - - * - - - *
- - - - - - * - - - - * - - - + - - - +
- - - - - - - - - - - - * - + + * - + +
- - - - - - - - - - - - * - - - * - + +
Continuing on, we are left with:
Level 1 Level 2 Level 3 Level 4 Level 5
+ + - - + + + + - * - + - - - + - - - +
- - - - - - + - - - - + - - - + - - - +
- - - - - - - - - - - - * - + + * - + +
- - - - - - - - - - - - * - - - * - + +
We must now inject to fill the remaining *'s. We pick (0, 3) and proceed:
Level 1 Level 2 Level 3 Level 4 Level 5
+ + - - + + + + - * - + - - - + - - - +
- - - - - - + - - - - + - - - + - - - +
- - - - - - - - - - - - + - + + + - + +
- - - - - - - - - - - - + - - - + - + +
And again, we pick (1, 0), and we are completely filled:
Level 1 Level 2 Level 3 Level 4 Level 5
+ + - - + + + + - + - + - - - + - - - +
- - - - - - + - - - - + - - - + - - - +
- - - - - - - - - - - - + - + + + - + +
- - - - - - - - - - - - + - - - + - + +
Thus, we have 3 required injection points, and the method returns 3.