PROBLEM STATEMENT
As part of a colonization effort two competing planets (planet X and planet O
(capital letter o)) send probes to an uninhabited moon with a conveniently
rectangular surface. Each of these probes (which landed at the center of
conveniently located unit squares) mine the lunar surface and build 4 new
probes. After two weeks the 4 new probes are completed and dispatched one unit
to the north, south, east, and west of the constructing probe. If a probe is
dispatched to a location that is already occupied or a location off of the
lunar surface, it becomes confused and self-destructs. The remaining new
probes then begin another two week cycle of mining, building, and dispatching.
Planet X delivered their probes exactly one week ahead of planet O. The probes
take negligible time (assume zero time) to travel to their new location and
begin the next cycle. If weeks are numbered such that planet X's original
probes were delivered at the beginning of week 1 then planet O's initial probes
arrive at the beginning of week 2, all new planet X probes will be completed at
the beginning of an odd numbered week (3, 5, 7, ..), and all new planet O
probes will be completed at the beginning of an even numbered week (4, 6, 8, ..).
Given the initial location of the probes and the dimensions of the lunar
surface, you are to compute the area of the moon that will eventually be
covered by probes from planet X.
If the lunar surface has dimensions 5x5, planet X originally dispatches probes
to 1,3 and 3,2, and planet O originally dispatches a probe to 1,1, then the
colonization proceeds as follows (X and O indicate that a unit of the lunar
surface occupied by a probe from planet X and planet O, respectively):
---- start of week 1 : X's first generation of probes arrive
|
| ---- start of week 2: O's first generation of probes arrive
| |
| | ---- start of week 3: X's second generation of probes is
completed and dispatched
| | |
| | | ---- start of week 4: O's second generation of
probes is dispatched
| | | |
| | | | ---- start of week 5: X dispatches the
third generation
| | | | |
| | | | | ---- start of week 6: O dispatches
the third generation
| | | | | |
| | | | | | ---- start of week 7: the
entire moon is colonized
| | | | | | |
..... ..... .X... .X... XXXX. XXXX. XXXXX
.X... .X... XXXX. XXXX. XXXXX XXXXX XXXXX
...X. ...X. .XXXX .XXXX XXXXX XXXXX XXXXX
..... .O... .O.X. OOOX. OOOXX OOOXX OOOXX
..... ..... ..... .O... .O.X. OOOX. OOOXX
After complete colonization planet X's probes have covered 19 of the 25 units
of area, so your method should return 19.
DEFINITION
Class: PlanetX
Method: colonize
Parameters: int, int, String[], String[]
Returns: int
Signature: int colonize(int width, int height, String[] xprobes, String[]
oprobes);
(make sure your method is public)
TopCoder will ensure the following:
- width will be between 1 and 10000 inclusive.
- height will be between 1 and 10000 inclusive.
- coordinates will be specified as "X Y" (double quotes for clarity only),
where X is the X coordinate in the range 0..width-1 (inclusive) and Y is the Y
coordinate in the range 0..height-1 (inclusive).
- X and Y are separated by a single space.
- there is no leading space before X or trailing space after Y.
- both X and Y will be represented using as few decimal digits as possible
(no extra leading zeros).
- xprobes will contain between 1 and 10 (inclusive) coordinate strings, all
unique.
- oprobes will contain between 1 and 10 (inclusive) coordinate strings, all
unique.
- xprobes and oprobes will not contain coordinates in common.
NOTES
- Your method should return the area of the lunar surface colonized by planet
X as an integral value between 0 and width * height (inclusive).
- Coordinates are measured with (0,0) being the unit square in the southwest
corner and (width-1,height-1) being the unit square in the northeast corner.
Coordinates will be specified as two integral values (with no leading zeros)
separated by a single space.
EXAMPLES
The example above corresponds to the inputs width=5, height=5, xprobes={"1
3","3 2"}, and oprobes={"1 1"}. Your method should return 19.
If width=1000, height=1000, xprobes={"0 1","1 0","1 1"}, and oprobes={"0 0"},
then planet X's probes have completely boxed in the probe from planet O. In
time planet X will completely take over the lunar surface except for the
original probe from planet O, so your method should return 999999.
If width=10000, height=10000, xprobes={"9999 9999"}, and oprobes={"0 0"}, your
method should return 50005000.
If width=20, height=30, xprobes={"4 8","19 0","19 2","17 27"}, and oprobes={"1
3","14 14","8 12"}, your method should return 359.