## BSSPC '21 J3 - Magic Paint Gun Cartridges

View as PDF

Points: 5
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Minestro is recreating images on the Internet with his magic paint gun when he unexpectedly runs out of cartridges!

Minestro has access to a supply of cartridges in the three primary colors - red, blue and yellow. Each image is represented by a grid of rows and columns of cells that are all initially empty, with no paint of any color in any cell.

Minestro can consume a single paint cartridge with his gun to add paint of the color of the cartridge to a contiguous sequence of adjacent cells in a single row. It is possible for up to three cartridges to paint their color on the same cell, in which case the resulting color is a mixture of all colors applied, according to the following table:

Color Symbol Primary Colors to Mix
White . None
Red R Red
Blue U Blue
Yellow Y Yellow
Orange O Red and yellow
Green G Blue and yellow
Purple P Red and blue
Brown B Red, blue, and yellow

Minestro still has one image to paint, so he needs you to tell him the minimum number of red, yellow, and blue paint cartridges he needs to buy — paint cartridges are expensive!

Note: Some Python 2/3 solutions may require PyPy to pass.

#### Input Specification

The first line will contain two integers and , the number of columns and rows of cells in the image, respectively.

The next lines will each contain characters, each of which is one of the eight characters ., R, O, Y, G, U, P, or B. The character on the line represents the required color of the cell on the row.

#### Output Specification

Output the minimum number of red, yellow, and blue paint cartridges Minestro needs to buy to paint the picture, separated by spaces.

6 4
..RR.P
..OORO
BBB.UU
ROBB..

5 4 4

#### Explanation for Sample Output 1

Minestro needs red cartridges: for the first row and in every other row. He needs yellow cartridges: in the second row and each in the last two rows. blue cartridges are used: in the first row, in the third, and in the last.

#### Sample Input 2

18 9
.B................
..YY...........YYY
...YYY.....YYYY...
..YYYYYYYYYYYYY...
.YYBBYYYYYBBYYY...
.RRYYYYBYYYYRRY...
.RRYYYOOOYYYRRY...
..YYYYOOOYYYYYY...
.YYYYYYYYYYYYYY...

10 13 4

#### Explanation for Sample Output 2

Minestro needs:

• red cartridges: in the first row, in the fifth, in the sixth, in the seventh, and in the eighth row.
• yellow cartridges: in the first row, in the second and third each, in the fourth and fifth each, in the sixth and seventh each, and cartridge each for the last two rows.
• blue cartridges: in the first row, in the fifth, and in the sixth row.