P7668 [JOI 2018 Final] Dango Maker / Dango Maker

You are a professional confectioner who makes dango (Japanese sweet dumplings). Now, you are going 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 red ($\texttt{R}$), green ($\texttt{G}$), or white ($\texttt{W}$). You will choose three consecutive dumplings from the cells and skewer them onto one stick. The direction of the chosen three consecutive dumplings must be left to right, or top to bottom. Now, you want to make dango sticks whose colors, in this order, are red, green, and white. You want to make as many dango sticks as possible. The order of dumplings on the stick must be the same as the order of the dumplings selected from the cells. A dumpling cannot be used on more than one stick. Given the colors of the dumplings placed on the grid, write a program to compute the maximum number of dango sticks you can make. The colors must be red, green, white in this order.

The first line of input contains two space-separated integers $N$ and $M$. Each of the next $N$ lines contains a string of length $M$, consisting of $\texttt{R}$, $\texttt{G}$, or $\texttt{W}$. The $j$-th character of this string is the color of the dumpling in the $i$-th row from the top and the $j$-th column from the left.

Print one integer: the maximum number of dango sticks.

#### Constraints For $100\%$ of the testdata, $1 \leq N \leq 3000$, $1 \leq M \leq 3000$, $1 \leq i \leq N$, $1 \leq j \leq M$. - Subtask $1$ ($13$ points): $N \leq 4$, $M \leq 4$. - Subtask $2$ ($20$ points): $N \leq 10$, $M \leq 10$. - Subtask $3$ ($67$ points): no additional constraints. #### Sample Explanation **For Sample $1$**: You can make $3$ dango sticks. - You choose three consecutive dumplings starting at the first row from the top and the first column from the left. The direction is left to right. Then you skewer them in this order. - You choose three consecutive dumplings starting at the first row from the top and the $4$-th column from the left. The direction is top to bottom. Then you skewer them in this order. - You choose three consecutive dumplings starting at the third row from the top and the first column from the left. The direction is left to right. Then you skewer them in this order. Since you cannot make $4$ sticks, the output is $3$. **For Sample $2$**: You can make $4$ dango sticks. - You choose three consecutive dumplings starting at the first row from the top and the first column from the left. The direction is left to right. Then you skewer them in this order. - You choose three consecutive dumplings starting at the first row from the top and the $4$-th column from the left. The direction is top to bottom. Then you skewer them in this order. - You choose three consecutive dumplings starting at the second row from the top and the second column from the left. The direction is top to bottom. Then you skewer them in this order. - You choose three consecutive dumplings starting at the second row from the top and the third column from the left. The direction is top to bottom. Then you skewer them in this order. Since you cannot make $5$ sticks, the output is $4$. #### Problem Note This problem comes from T3: Dango Maker of The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round: [T3: Dango Maker](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t3-en.pdf). Translated and整理 (pinyin: zhengli, compiled/organized) by @[求学的企鹅](/user/271784). Translated by ChatGPT 5