시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 316 | 103 | 88 | 33.333% |
You are a professional confectioner making dangos, Japanese sweet dumplings. Now, you are about to skewer the dumplings.
The dumplings are placed on a grid of cells with N rows and M columns. Each cell contains one dumpling. The color of each dumpling is either red (R), green (G), or white (W).
You will choose three consecutive dumplings from the cells, and skewer them to a stick. The direction of the chosen three consecutive dumplings must be from left to right, or from top to bottom.
Now, you want to make sticks of dumplings whose colors are red, green, white, in this order. You want to make as many sticks of dumplings as possible. The order of dumplings skewered to a stick must be the same as the order of dumplings chosen from the cells. You are not allowed to skewer more than one sticks to one dumpling.
How many sticks of dumplings can you make?
Given the colors of dumplings placed on the cells, write a program which calculates the maximum number of sticks of dumplings you can make. The colors must be red, green, white, in this order.
Read the following data from the standard input.
White one line to the standard output. The output should contain the maximum number of sticks of dumplings.
번호 | 배점 | 제한 |
---|---|---|
1 | 13 | N ≤ 4, M ≤ 4. |
2 | 20 | N ≤ 10, M ≤ 10. |
3 | 67 | There are no additional constraints. |
3 4 RGWR GRGG RGWW
3
By the following way, you can make 3 sticks of dumplings.
Since you cannot make 4 sticks, output 3.
4 4 RGWR GRRG WGGW WWWR
4
By the following way, you can make 4 sticks of dumplings.
Since you cannot make 5 sticks, output 4.
5 5 RGRGW GRRGW WGGWR RWRGW RGWGW
6