TopcoderArchiveVisit Topcoder
Archive
SRM2 Jan 2003
SRM 127

ColorCount

Problem statement, definition, constraints, and public examples.

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.

Definition

Class:
ColorCount
Method:
howMany
Parameters:
int, String[]
Returns:
String[]
Method signature:
String[] howMany(int size, String[] commands)
(be sure your method is public)

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

  1. 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"} 
  2. 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 
  3. 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. 
  4. 1000000000
    {"FLOODFILL 123456789 987654321 7"}
    Returns: { "0",  "0",  "0",  "0",  "0",  "0",  "0",  "1000000000000000000",  "0",  "0" }
  5. 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" }
  6. 123456789
    {"PIXEL 7380411 3540877 2",
 "PIXEL 58987273 87063849 7",
 "PIXEL 32377351 91388577 0",
 "PIXEL 113368450 101337231 2",
 "PIXEL 4571176 104059491 0",
 "PIXEL 104674582 110537835 9",
 "PIXEL 80005876 118683523 7",
 "PIXEL 101767677 45263703 7",
 "PIXEL 27124012 94553103 4",
 "PIXEL 100405719 16089343 4",
 "PIXEL 32131597 46997466 6",
 "PIXEL 35214605 109876887 6",
 "PIXEL 81853811 116138268 8",
 "PIXEL 46533511 34287607 5",
 "PIXEL 13379417 72005814 3",
 "PIXEL 121707460 39451044 1",
 "PIXEL 27315801 108416333 5",
 "PIXEL 32097321 107157333 3",
 "PIXEL 72728947 21947328 6",
 "PIXEL 39944023 7162323 3",
 "PIXEL 64239805 3272861 8",
 "PIXEL 49600969 18647539 5",
 "PIXEL 95654766 48588373 3",
 "PIXEL 58385324 109436562 1",
 "PIXEL 76060621 17310784 1",
 "PIXEL 56428047 18387412 9",
 "PIXEL 19760035 74667740 0",
 "PIXEL 39327810 30127890 4",
 "PIXEL 49677004 95737619 1",
 "PIXEL 13912485 10360741 0",
 "PIXEL 25941909 118063929 1",
 "PIXEL 117990535 77282759 1",
 "PIXEL 31901665 111872258 1",
 "PIXEL 23089746 101226729 7",
 "PIXEL 65473100 18299657 2",
 "PIXEL 119707341 94812645 4",
 "PIXEL 86382327 18260783 9",
 "PIXEL 105322655 108328088 9",
 "PIXEL 121150976 83902457 2",
 "PIXEL 117165376 9645933 9",
 "PIXEL 97623536 23343297 1",
 "PIXEL 62199947 46286522 1",
 "PIXEL 81636055 114242356 0",
 "PIXEL 34831842 54317014 9",
 "PIXEL 110045475 2153807 4",
 "PIXEL 120406581 58886128 0",
 "PIXEL 102800404 112475709 2",
 "PIXEL 9365537 117466680 0",
 "PIXEL 122097557 12777773 5",
 "RECT 123456 789123 93879879 4328743 1"}

    Returns: { "14909716542915177",  "331862207275313",  "4",  "4",  "5",  "4",  "3",  "4",  "1",  "6" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.

Back to all problems