PROBLEM STATEMENT
You are given the dimensions of a farm as dimX (breadth) and dimY(length). You
want to plow a single rectangular section of this farm. The farm might have
some boulders in it. The boulders cannot be plowed and since you can only plow
a single rectangular region you need to find the area of the biggest clean
rectangular section of the farm. A piece of farm is clean if it has no boulders
in it.
Create a class Farm that contains a method cleanRect, which takes two integers
dimX,dimY and a String[] boulders as input and returns the integer area of the
biggest clean rectangular section in a farm of dimension dimX times dimY.
DEFINITION
Class: Farm
Method name: cleanRect
Parameters: int, int, String[]
Returns: int
Method signature(be sure your method is public): int cleanRect(int dimX,int
dimY,String[] boulders)
NOTES
- Each element of boulders corresponds to location of a boulder in the farm.
- x and y signify the coordinate of the boulder about the X and Y axis
respectively.
- The top left grid-block of the farm has coordinates "0,0". X coordinates
increase rightwards and Y coordinates increase downwards.
- Each boulder occupies the complete grid-block in the farm it lies on.
- Only those rectangles whose sides are oriented parallel to the X or the Y
axis are to be considered.
- If no clean rectangular region is available return 0.
- There can be more than one boulders on the same location.
Topcoder will ensure the validity of the inputs. Inputs are valid if all the
following criteria are met:
- boulders has 0 to 50 elements (inclusive).
- dimX is between 1 and 9999 (inclusive).
- dimY is between 1 and 9999 (inclusive).
- Each element of boulders is of the form "x,y" (a string containing two
non-negative integers separated with a single comma).
- For each element of boulders: x is between 0 and dimX-1 (inclusive).
- For each element of boulders: y is bteween 0 and dimY-1 (inclusive).
EXAMPLES
Example 1: Here's an example with
dimX = 7
dimY = 5
boulders = {"5,1","3,4"}
In this case the farm looks like
-------
-----B-
-------
-------
---B---
where '-' is the plain land and 'B' is the boulder.
In this case the biggest clean rectangle will be
CCCCC--
CCCCCB-
CCCCC--
CCCCC--
---B---
where 'C' is a grid-block in the biggest clean rectangle.
hence your method should return 20.
Example 2:
dimX = 5
dimY = 3
boulders = {"2,2"}
In this case the farm would look like
CCCCC
CCCCC
--B--
hence your method should return 10.
Example 3:
dimX = 2
dimY = 2
boulders = {"0,0","1,1","0,1"}
In this case the farm would look like
BC
BB
hence your method should return 1.