BSSPC '21 J3 - Magic Paint Gun Cartridges

View as PDF

Submit solution


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 N rows and M 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.

Constraints

1 \le M, N \le 1\,000

Input Specification

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

The next N lines will each contain M characters, each of which is one of the eight characters ., R, O, Y, G, U, P, or B. The v^{th} character on the i^{th} line represents the required color of the v^{th} cell on the i^{th} 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.

Sample Input 1

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

Sample Output 1

5 4 4

Explanation for Sample Output 1

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

Sample Input 2

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

Sample Output 2

10 13 4

Explanation for Sample Output 2

Minestro needs:

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

Comments

There are no comments at the moment.