Connection Status:
Competition Arena > ColorCount

ColorCount

SRM 127 · 2003-01-02 · by Yarin

SRM 127 · 2003-01-02 · by Yarin
Class Name: ColorCount
Return Type: String[]
Method Name: howMany
Arg Types: (int, vector<string>)
Problem Statement

Problem Statement

Most painting programs have a feature which counts how many pixels of each color a picture has. You are to simulate this feature on a large picture after a number of drawing commands have been executed. The drawing commands may be one of the following: (quotes are for clarity only)

  • "PIXEL <x> <y> <c>" Puts a pixel with color c at coordinate x,y.
  • "HLINE <x1> <y> <x2> <c>" Draws a horizontal line between x1,y and x2,y (inclusive) with color c.
  • "VLINE <x> <y1> <y2> <c>" Draws a vertical line between x,y1 and x,y2 (inclusive) with color c.
  • "RECT <x1> <y1> <x2> <y2> <c>" Draws a filled rectangle with the opposite corners x1,y1 and x2,y2 (inclusive) using color c.
  • "FLOODFILL <x> <y> <c>" Turns every pixel that belongs to the same region as x,y into color c. Two pixels belong to the same region if they have the same color and are adjacent to each other vertically or horizontally. In other words, two points are in the same region if and only if: 1) The two points have the same color c and 2) There exists a path connecting the two, consisting of only horizontal and vertical steps across pixels that all have color c.

There will be exactly one space between each term in the command, and a command will not contain leading or trailing spaces. All numbers will be integers without unnecessary leading zeros.

Create a class ColorCount containing the method howMany which takes as parameters an int size, the size of the picture (a square bitmap with sides of length size, all pixels initially being of color 0) and a String[] commands, in which each element is a drawing command in the format above. The method should return a String[] containing for each color 0 to 9, inclusive, how many pixels are of that color (element i in the return value should correspond to color i). Each element in the return variable should be an integer with no unnecessary leading zeros, and contain no other characters than digits.

Notes

  • All pixels initially have color 0.
  • If a pixel has a particular color, and is later given a different color, the pixel takes the last color it was given.
  • The top left corner of the picture has coordinates 0,0, the bottom right corner has coordinates size-1,size-1.
  • A line may have length 1.
  • A rectangle may have area 1.
  • The 64 bit datatype for C++ is long long.

Constraints

  • size will be between 1 and 1000000000, inclusive.
  • commands will contain between 0 and 50 elements, inclusive.
  • Each element in commands will be in one of forms mentioned above.
  • All parameters in commands refering to pixel coordinates will be between 0 and size-1, inclusive.
  • All parameters in commands refering to color values will be between 0 and 9, inclusive.
  • There will be no unnecessary leading zeros in the coordinates or color values.
Examples
0)
2
{"PIXEL 0 0 1",
 "PIXEL 0 0 2"}
Returns: { "3",  "0",  "1",  "0",  "0",  "0",  "0",  "0",  "0",  "0" }

This bitmap contains four pixels, all initially having color 0. First we change pixel 0,0 to color 1, and then we put a new pixel at the same position having color 2. We then have 1 pixel with color 2 and 3 pixels with the initial color 0, so the method should return {"3","0","1","0","0","0","0","0","0","0"}

1)
8
{"VLINE 0 4 1 1",
 "RECT 4 2 7 4 3",
 "RECT 6 7 7 3 4",
 "PIXEL 1 7 5",
 "PIXEL 1 5 7",
 "PIXEL 2 6 6",
 "FLOODFILL 1 6 8",
 "FLOODFILL 5 3 9",
 "HLINE 4 6 7 3"}
Returns: { "33",  "4",  "0",  "4",  "8",  "1",  "1",  "1",  "4",  "8" }

After these commands, the image will look like this: 00000000 10000000 10009999 10009944 10009944 87000044 88603333 85000044

2)
10000
{"VLINE 3000 0 9999 1",
 "FLOODFILL 2999 3000 2",
 "FLOODFILL 3001 3000 3",
 "FLOODFILL 8000 8000 3"}
Returns: { "0",  "10000",  "30000000",  "69990000",  "0",  "0",  "0",  "0",  "0",  "0" }

This is just a vertical line splitting the image into two parts.

3)
1000000000
{"FLOODFILL 123456789 987654321 7"}
Returns: { "0",  "0",  "0",  "0",  "0",  "0",  "0",  "1000000000000000000",  "0",  "0" }
4)
100000
{"FLOODFILL 37769 39643 7",
 "HLINE 50504 81820 83834 7",
 "VLINE 71737 26731 32081 4",
 "VLINE 40181 59753 84556 3",
 "FLOODFILL 59627 26109 8",
 "PIXEL 91036 18017 5",
 "PIXEL 44303 47855 9",
 "PIXEL 39359 35545 2",
 "HLINE 53095 35062 43335 7",
 "FLOODFILL 21335 15869 6",
 "RECT 90904 236 71131 85564 9",
 "RECT 58469 48134 48997 3140 3",
 "HLINE 86899 32098 77083 7",
 "HLINE 52123 73414 26366 7",
 "FLOODFILL 63197 10509 4",
 "PIXEL 71698 25443 5",
 "VLINE 7501 35275 7806 5",
 "HLINE 17069 41178 27200 8",
 "FLOODFILL 25237 57070 6",
 "PIXEL 24317 52234 1",
 "VLINE 767 48764 66613 8",
 "FLOODFILL 82305 89350 4",
 "RECT 88207 2494 86147 52329 8",
 "RECT 30817 93708 26912 92914 4",
 "VLINE 37896 11144 5573 5"}
Returns: { "0",  "1",  "1",  "426262438",  "7886349468",  "33044",  "0",  "40484",  "102739978",  "1584574586" }

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

Coding Area

Language: C++17 · define a public class ColorCount with a public method vector<string> howMany(int size, vector<string> commands) · 25 test cases · 2 s / 256 MB per case

Submitting as anonymous