BSSPC '21 J3 - Magic Paint Gun Cartridges - DMOJ: Modern Online Judge

BSSPC '21 J3 - Magic Paint Gun Cartridges

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$ ~N~ rows and $M$ ~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$ ~1 \le M, N \le 1\,000~

Input Specification

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

The next $N$ ~N~ lines will each contain $M$ ~M~ characters, each of which is one of the eight characters ., R, O, Y, G, U, P, or B. The $v^{th}$ ~v^{th}~ character on the $i^{th}$ ~i^{th}~ line represents the required color of the $v^{th}$ ~v^{th}~ cell on the $i^{th}$ ~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$ ~5~ red cartridges: $2$ ~2~ for the first row and $1$ ~1~ in every other row. He needs $4$ ~4~ yellow cartridges: $2$ ~2~ in the second row and $1$ ~1~ each in the last two rows. $4$ ~4~ blue cartridges are used: $1$ ~1~ in the first row, $2$ ~2~ in the third, and $1$ ~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$ ~10~ red cartridges: $1$ ~1~ in the first row, $2$ ~2~ in the fifth, $3$ ~3~ in the sixth, $3$ ~3~ in the seventh, and $1$ ~1~ in the eighth row.
$13$ ~13~ yellow cartridges: $1$ ~1~ in the first row, $2$ ~2~ in the second and third each, $1$ ~1~ in the fourth and fifth each, $2$ ~2~ in the sixth and seventh each, and $1$ ~1~ cartridge each for the last two rows.
$4$ ~4~ blue cartridges: $1$ ~1~ in the first row, $2$ ~2~ in the fifth, and $1$ ~1~ in the sixth row.

Comments

0

QiQi commented on Nov. 14, 2021, 8:51 p.m. ← edit 2 →

Deleted statement

1

Nils_Emmenegger commented on Nov. 14, 2021, 9:29 p.m.

You may find it useful to reread the statement. In particular:

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.

Happy coding!