Connection Status:
Competition Arena > ColoredStrokes

ColoredStrokes

SRM 496 · 2010-11-01 · by gojira_tc

SRM 496 · 2010-11-01 · by gojira_tc · Greedy, String Manipulation
Class Name: ColoredStrokes
Return Type: int
Method Name: getLeast
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Manao has a bitmap H pixels high and W pixels wide. Initially, each of the pixels is white. Manao draws several (possibly zero) horizontal and/or vertical strokes. A stroke is a line segment 1 pixel thick and 1 or more pixels long. Manao only draws horizontal strokes with red color and vertical strokes with blue. He can paint a one pixel long stroke with either red or blue color, and the stroke will be considered horizontal if red and vertical if blue. Manao never draws two horizontal or two vertical strokes that overlap. If a horizontal stroke and a vertical stroke cross, the pixel at their intersection becomes green.

You're given a String[] picture denoting the bitmap after Manao's drawing experiments. The x-th character of the y-th element of picture describes the color of the pixel at coordinates (x, y) of the bitmap, where (0, 0) is the pixel at the top left corner and (W-1, H-1) is the pixel at the bottom right corner. 'R' is red, 'G' is green, 'B' is blue and '.' is white. Return the least possible number of strokes needed to obtain the given picture.

Constraints

  • picture will contain between 1 and 50 elements, inclusive.
  • Each element of picture will be between 1 and 50 characters long, inclusive.
  • All elements of picture will have equal length.
  • Each character in picture will be 'R', 'G', 'B' or '.'.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{"...",
 "..."}
Returns: 0

The picture is blank, Manao made no strokes.

1)
{"RRB"}
Returns: 2
2)
{"..B.",
 "..B."}
Returns: 1

A single vertical stroke is enough.

3)
{"...B..",
 ".RRG.R",
 "...B.."}
Returns: 3
4)
{"G"}
Returns: 2
29)
{".BB."}
Returns: 2

Since only vertical strokes are painted with blue color, this picture needs two strokes.

30)
{"...B..",
 ".BRGRR",
 ".B.B.."}
Returns: 3

One horizontal and two vertical strokes are necessary for this masterpiece.

31)
{"...B..",
 ".BRBRR",
 ".B.B.."}
Returns: 4

This is the same picture as in the previous case with pixel (3,1) colored blue instead of green. Therefore, a single horizontal stroke won't help.

Submissions are judged against all 141 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ColoredStrokes with a public method int getLeast(vector<string> picture) · 141 test cases · 2 s / 256 MB per case

Submitting as anonymous