PROBLEM STATEMENT
You are given a picture that needs to be colored in. To aid in the coloring
process, color clues have been placed in the picture. To color a particular
region of the picture you must first locate the color clue with the highest
value within the region. In case of a tie the leftmost clue is chosen from
among the highest. For example:
XXXXXXXXXX
...2.X....
.2...X..2.
...0.XXXXX 'X's are boundaries
..1..X.... '.'s are blanks
.3...X....
....3X....
XXXXXXXXXX
Above there are 3 regions: the left, the upper right, and the lower right. The
lower right has no clues. The left does have clues so first we find the
highest clue value(3). There is a tie between two 3s in the region so the
leftmost 3 is chosen. The upper right does have a clue and we choose the
highest clue, which is also the only clue in the region(2).
Once we have chosen a clue for a region we ignore all other clues in that
region. Next, the point with the chosen clue on it is given the color value of
the clue. The picture before would now look like this once we have 1)chosen
clues, 2)ignored the unchosen, & 3)given the points corresponding to the chosen
clues the corresponding color values:
XXXXXXXXXX
.....X....
.....X..2.
.....XXXXX 'X's are boundaries
.....X.... '.'s are blanks
.3...X....
.....X....
XXXXXXXXXX
Finally we must ensure that the following criteria hold for the region:
1) All points in a region with the same horizontal coordinate share the same
color value.
2) A point in the region one step to the left of another point in the region
must have a color value lower by one.
3) A point in the region one step to the right of another point in the region
must have a color value higher by one.
The picture used before would be colored as follows:
XXXXXXXXXX
23456X0123
23456X0123
23456XXXXX 'X's are boundaries
23456X.... '.'s are blanks
23456X....
23456X....
XXXXXXXXXX
As can be seen, the coloring method creates something of a color gradient in
each region. The region on the lower right had no color clues so it could not
be colored and remains blank. Also note that all shading ends at the
boundaries of the picture. It is as if there is an imaginary boundary around
the outside of the picture. In other words, all regions that touch the edge of
the picture end at the edge of the picture.
Your method will color all of the regions in the picture that can be colored,
and will then return the sum of all of the colors values in the picture not
including blank regions and boundaries.
In the above example it would be:
6*(2+3+4+5+6) + 2*(0+1+2+3) = 132
Since the blank region and boundaries were disregarded, and there are 6 rows of
2+3+4+5+6 in the left region and 2 rows of 0+1+2+3 in the upper right region.
Two points are in the same region if and only if there exists a path between
them that does not cross a boundary. This path can only consist of vertical
and horizontal moves (no one step diagonal moves). This path must not contain
boundary symbols and cannot leave the picture.
Create a class NumberFill that contains the method gradient, which takes a
String[] picture and returns the sum of all colors values within the picture
once all regions that should be filled have been properly filled. Boundary
points and blank regions are not included in the summation calculation.
DEFINITION
Class: NumberFill
Method: gradient
Parameters: String[]
Returns: int
Method signature (be sure your method is public): int gradient(String[]
picture);
Boundaries are represented by 'X' characters.
Color clues are represented by characters '0'..'9' inclusive.
Blank spots on the board are represented by '.' characters.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- All characters in picture are either 'X', '.', or '0'..'9' inclusive (single
quotes for clarity)
- All elements of picture will have the same length.
- All elements of picture will have length between 1 and 20 inclusive
- picture will contain between 1 and 20 elements inclusive
NOTES
- Due to the nature of the process, negative color values and color values
greater than 9 can occur in the picture after the gradient has been computed
(see example 6 for more on negative color values)
EXAMPLES
1) picture = {
"..X.....",
"..X..0..",
"1.X.....",
"..X.....",
"........"}
The highest clue in the region is the 1 so it is chosen.
The final picture would look like:
12X45678
12X45678
12X45678
12X45678
12345678
The return value is thus: 5*(1+2+4+5+6+7+8)+3 = 168
2) picture = {
"5.X.....",
"..X..3..",
"..X.....",
"..X.....",
"..X....."}
There are two regions in this picture: the left and the right.
The highest clue in the left region is the 5 so it is chosen.
The highest clue in the right region is the 3 so it is chosen.
The final picture would look like:
56X12345
56X12345
56X12345
56X12345
56X12345
The return value is thus: 5*(5+6+1+2+3+4+5) = 130
3) picture = {
"........",
"........",
"........",
"........"}
There are no clues in the region so it is left blank.
The return value is thus: 0
4) picture = {"...3"}
The highest clue in the region is the 3 so it is chosen.
The final picture would look like:
0123
The return value is thus 0+1+2+3 = 6
5) picture = {".3....3"}
Two clues of value 3 are tied for the highest clue in the region. The leftmost
3 is chosen.
The final picture would look like:
2345678
The return value is thus 2+3+4+5+6+7+8 = 35
6) picture = {"......0"}
The highest clue in the region is the 0 so it is chosen.
The final picture would look like:
-6 -5 -4 -3 -2 -1 0
The return value is thus -6+-5+-4+-3+-2+-1+0 = -21