Problem Statement
In most painting programs there is an operation called fill that will color regions of a picture. This problem will deal with a variant of filling called precedence filling. The painting canvas will be modeled as a String[] where each character is a point in the painting. Fill works as follows:
A point x is reachable from another point y if there is a path consisting of only horizontal and vertical steps that will take you from y to x. In addition, x, y, and all of the intermediate points must have the same color.
If the operation fill is applied to a point y on the canvas, y and all points reachable from y will be given the fill color. The fill color is a color designated when the fill is applied.
In this problem, the colors on the canvas will have different priorities. The priorities will be given in a String[] rules. The colors we are dealing with will be denoted by uppercase letters ('A'-'Z'). rules will contain elements of the form (quotes for clarity) "C > C" where the C's will be distinct uppercase letters. For example, "A > B" would mean color A has a higher precedence than color B. In addition, precedence is transitive. So, if "A > B" and "B > C" are in rules you can infer that A has precedence over C. We can now define precedence filling:
A point x is p-reachable from another point y if there is a path consisting of only horizontal and vertical steps that will take you from y to x. In addition, x, and all of the intermediate points must each have colors of lower precedence than y or be the same color as y.
If the operation precedence fill is applied to a point y on the canvas, y and all points p-reachable from y will be given the fill color. The fill color is a color designated when the fill is applied.
You will be given a String[] canvas, 0-based ints row and column, a String[] rules, and a char fillColor. You will return a String[] depicting the canvas after a precedence fill has occurred at the specified row and column using the fillColor. The point at row i column j is character j in element i of canvas.
A point x is reachable from another point y if there is a path consisting of only horizontal and vertical steps that will take you from y to x. In addition, x, y, and all of the intermediate points must have the same color.
If the operation fill is applied to a point y on the canvas, y and all points reachable from y will be given the fill color. The fill color is a color designated when the fill is applied.
In this problem, the colors on the canvas will have different priorities. The priorities will be given in a String[] rules. The colors we are dealing with will be denoted by uppercase letters ('A'-'Z'). rules will contain elements of the form (quotes for clarity) "C > C" where the C's will be distinct uppercase letters. For example, "A > B" would mean color A has a higher precedence than color B. In addition, precedence is transitive. So, if "A > B" and "B > C" are in rules you can infer that A has precedence over C. We can now define precedence filling:
A point x is p-reachable from another point y if there is a path consisting of only horizontal and vertical steps that will take you from y to x. In addition, x, and all of the intermediate points must each have colors of lower precedence than y or be the same color as y.
If the operation precedence fill is applied to a point y on the canvas, y and all points p-reachable from y will be given the fill color. The fill color is a color designated when the fill is applied.
You will be given a String[] canvas, 0-based ints row and column, a String[] rules, and a char fillColor. You will return a String[] depicting the canvas after a precedence fill has occurred at the specified row and column using the fillColor. The point at row i column j is character j in element i of canvas.
Definition
- Class:
- TransFill
- Method:
- fill
- Parameters:
- String[], int, int, String[], char
- Returns:
- String[]
- Method signature:
- String[] fill(String[] canvas, int row, int column, String[] rules, char fillColor)
- (be sure your method is public)
Notes
- Precedence rules are transitive, but they need not adhere to any other restrictions. In other words "A > B","B > A" can both exist simultaneously as valid rules. In addition, "A > A" is a valid rule.
Constraints
- Let height denote the number of elements in canvas and width denote the number of characters in each element of canvas
- height will be between 2 and 50 inclusive
- width will be between 2 and 50 inclusive
- Each element of canvas will contain exactly width characters
- Each character in each element of canvas will be a uppercase letter ('A'-'Z')
- row will be between 0 and height-1 inclusive
- column will be between 0 and width-1 inclusive
- rules will contain between 0 and 50 elements inclusive
- Each element of rules will contain exactly 5 characters
- Characters 0 and 4 of each element of rules will be uppercase letters ('A'-'Z')
- Characters 1 and 3 of each element of rules will be spaces
- Character 2 of each element of rules will be a greater than symbol ('>')
- Each element of rules will be distinct
- fillColor will be a capital letter ('A'-'Z')
Examples
{"AAA", "AAA", "AAA"}0
0
{}'B'
Returns: { "BBB", "BBB", "BBB" }The entire canvas is p-reachable.{"BBB", "ABB", "BBB"}1
0
{}'C'
Returns: { "BBB", "CBB", "BBB" }The 'B's are uncolorable.{"ABBBB", "BBBDD", "DDDDB", "EEEEE", "DDDDD"}0
0
{"A > B","A > C","B > D"}'F'
Returns: { "FFFFF", "FFFFF", "FFFFF", "EEEEE", "DDDDD" }Since A > B and B > D, the top 3 rows are p-reachable. The rest cannot be filled. Note that the B in the third row is filled.{"AA","AA"}1
1
{"A > A"}'B'
Returns: { "BB", "BB" }{"BBB", "BAB", "BBB"}1
1
{"C > B"}'C'
Returns: { "BBB", "BCB", "BBB" }
Back to all problems