PROBLEM STATEMENT
The speed of a video card is largely dependent on its fill rate, or the number
of pixels drawn per second. In order to calculate the fill rate, you need to
know how many pixels were actually drawn by the video card, including ones that
might have been overdrawn.
Given a screenshot of a scene (image) made up exclusively of overlapping
rectangles, return the minimum number of pixels that were drawn (including
overlap).
There will be up to 26 rectangles, A-Z, with no two rectangles being
represented by the same letter. "." will represent a black background where
nothing is drawn.
For illustrative purposes, the examples will refer to pixels and rectangles in
the image specifically.
(a,b) refers to a pixel 'a' to the right and 'b' down, with (0,0) as the upper
left corner.
axb refers to a rectangle 'a' pixels wide and 'b' pixels high.
If the image can't be created using only one rectangle per letter, return -1,
as in:
..XXX
..XXX
XX...
The rectangles must be ordered to represent a valid image, but can appear in
ANY order (not just alphabetical). It is valid if "A" is drawn before "B", or
if "B" is drawn before "A", but not if both are true. If the rectangles have
no valid ordering, return -1.
As an example, see the following image:
.DD.BB.
ADDAAAA
ADDAAAA
.DD.BB.
CCCCBBC
CCCCBBC
.DD.BB.
D was drawn before C, C was drawn before B, B was drawn before A, and A was
drawn before D - your method would return -1.
Lets say we have:
YY. and ...
YY. and .XX
... and .XX
If the first one was drawn, followed by the second one, you would see:
YY.
YXX
.XX
Given this picture, you could determine the minimum shape of the two
rectangles. Since 4 were required for X, and 4 for Y, the return value would
be 8.
Suppose the input was:
AAY
AAY
YYA
Since there are either two A rectangles (2x2 and 1x1) on a Y rectangle (3x3) or
two Ys (1x2 and 2x1) on an A (3x3). Because there is a limit of one rectangle
for each letter, the image is invalid and your method would return -1.
DEFINITION
Class: FillRate
Method: numPixels
Parameters: String[]
Returns: int
Method signature (be sure your method is public): int numPixels(String[] pixels);
NOTES
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met
- pixels will have between 1 and 20 elements, inclusive
- each element of pixels will be a String of length 1 to 20, inclusive
- each element of pixels will have the same length
- each String in pixels will be made up of only the uppercase letters A-Z and "."
EXAMPLES
For illustrative purposes, the examples will refer to points in the image.
(a,b) refers to a pixel 'a' to the right and 'b' down, with (0,0) as the upper
left corner.
axb refers to a rectangle 'a' pixels wide and 'b' pixels high.
----------------------------------------------------------------
Example 1:
Input:
XX..
XX..
...Y
..YY
Because "." represents black and an undrawn spot at (2,2) where the Y rectangle
should be drawn, this is an invalid image.
The method would return -1.
----------------------------------------------------------------
Example 2:
Input:
ABCD
EFGH
IJAK
LMNO
Because "A" appears at (0,0) and at (2,2), it has to be a minimum of 3x3, and
the others must be a minimum of 1x1.
A has size 9, B through O have size 1, for a total size of 23.
The method would return 23.
----------------------------------------------------------------
Example 3:
Input:
XXXX..
XXXXBB
XXXXBB
XXXXAB
CCCAA.
Notes:
X has to be a minimum of 4x4 = 16
B has to be a minimum of 2x3 = 6
A has to be a minimum of 2x2 = 4
C has to be a minimum of 3x1 = 3
16 + 6 + 4 + 3 = 29
The method would return: 29
----------------------------------------------------------------
MORE EXAMPLES
Input:
.D..B.
AAAABA
.D..B.
CCCCCC
.D..B.
The method would return: 22
Input:
.D..B.
AAAABA
.D..B.
CDCCCC
.D..B.
The method would return: -1 (A was drawn before B was drawn before C was drawn
before D was drawn before A - this is illegal)