P7668 [JOI 2018 Final] 团子制作 / Dango Maker

你是一名专业的糕点师，制作团子，日本甜饺子。现在，你要串饺子了。

饺子被放置在具有 $N$ 行和 $M$ 列的单元格网格上。每个单元格包含一个饺子。每个饺子的颜色是红色（$\texttt{R}$）、绿色（$\texttt{G}$）或 白色（$\texttt{W}$）。 您将从单元格中选择三个连续的饺子，并将它们串成一根棍子。所选的三个连续饺子的方向必须是从左到右，或从上到下。 现在，您要按此顺序制作颜色为红色、绿色、白色的饺子串。你想做尽可能多的饺子串。串到棍子上的饺子的顺序必须与从单元格中选择的饺子的顺序相同。一个饺子上不能串多根棍子。 你能做多少串饺子？ 现给定放置在单元格上的饺子的颜色，请编写一个程序来计算您可以制作的饺子的最大数量。颜色必须按此顺序为红色、绿色、白色。

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。接下来的 $N$ 行的第 $i$ 行包含大小为 $M$ 的字符串，由 $\texttt{R}$、$\texttt{G}$ 或 $\texttt{W}$ 组成。该字符串的第 $j$ 个字符是从上数第 $i$ 行、从左数第 $j$ 列的饺子的颜色。

输出一个整数饺子串的最大数量。

#### 数据规模与约定 对于 $100 \%$ 的数据，$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）：没有额外的限制。 #### 样例说明 **对于样例 $1$**：你能制作 $3$ 串饺子。 - 您从顶部的第一行和左侧的第一列中选择三个连续的饺子。方向是从左到右。然后，你按照这个顺序把它们串成一串。 - 您从上数第一行和左数第 $4$ 列中选择三个连续的饺子。方向是从上到下。然后，你按照这个顺序把它们串成一串。 - 您从上数第三行和左数第一列中选择三个连续的饺子。方向是从左到右。然后，你按照这个顺序把它们串成一串。 因为你不能做 $4$ 串，所以输出 $3$。 **对于样例 $2$**：你能制作 $4$ 串饺子。 - 您从顶部的第一行和左侧的第一列中选择三个连续的饺子。方向是从左到右。然后，你按照这个顺序把它们串成一串。 - 您从顶部的第一行和左侧的第 4 列中选择三个连续的饺子。方向是从上到下。然后，你按照这个顺序把它们串成一串。 - 您从上数第二行和左数第二列中选择三个连续的饺子。方向是从上到下。然后，你按照这个顺序把它们串成一串。 - 您从上数第二行和左数第三列中选择三个连续的饺子。方向是从上到下。然后，你按照这个顺序把它们串成一串。 因为你不能做 $5$ 串，所以输出 $4$。 #### 题目说明： 来源于 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)。 由 @[求学的企鹅](/user/271784) 翻译整理。