団子職人 (Dango Maker)

### 题目描述 你是一个包団子（日本传统食物，不要在意）的工匠。现在你要把団子串起来了。 所有的団子都放在一个正方形中，分为 $N$ 行和 $M$ 列。 每个点上有 $1$ 个団子。 每个団子的颜色为红色（R）、绿色（G）或白色（W）其中一种。你可以从左到右或从上到下连续取出 $3$ 个団子，然后按取出的顺序将 $3$ 个団子粘在 $1$ 个串上。 现在你想串尽可能多的串，但这些串上的団子必须按照 $1$ 个红、$1$ 个绿、$1$ 个白的顺序。另外，一个団子只能放在一个串上。 ### 输入格式 第一行为 $N$ 和 $M$，意义如上所述。 第二行到第 $N+1$ 行，每行 $M$ 个字符，代表団子的排列。 ### 输出格式 输出一个整数，代表你能串的最多的串数。

[problemUrl]: https://atcoder.jp/contests/joi2018ho/tasks/joi2018ho_c あなたは団子を作る職人である．今，あなたは団子に串を刺そうとしているところである． 団子は，縦 $ N $ 行，横 $ M $ 列に仕切られたマスの中に配置されている．各マスには団子が $ 1 $ 個ずつ入っている．それぞれの団子には，赤 (R)，緑 (G)，白 (W) のいずれかの色が付いている．あなたは，左から右の方向，または，上から下の方向に連続する $ 3 $ マスから団子を取り出し，この順に $ 1 $ 本の串にちょうど $ 3 $ 個刺すことができる． 今あなたは，赤，緑，白の団子が $ 1 $ 個ずつこの順に刺さった串を可能な限り多く作りたい．串に刺す順番は，マスから取り出した順番と同じでなければならない．また，同じ団子に $ 2 $ 本以上の串を刺すことはできない． あなたは，団子が刺さった串を最大何本作ることができるだろうか．

標準入力から以下の入力を読み込め． - $ 1 $ 行目には，整数 $ N $ と $ M $ が空白を区切りとして書かれている． - 続く $ N $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N $) には，`R`, `G`, `W` からなる長さ $ M $ の文字列が書かれている．この文字列の $ j $ 文字目 ($ 1\ \leqq\ j\ \leqq\ M $) は，上から $ i $ 行目，左から $ j $ 列目のマスの団子の色を表す．

標準出力に，団子が刺さった串の本数の最大値を $ 1 $ 行で出力せよ． - - - - - -

3 4
RGWR
GRGG
RGWW

3

4 4
RGWR
GRRG
WGGW
WWWR

4

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW

6

### 課題 マスの中に配置された団子の色の情報が与えられたとき，赤，緑，白の団子が $ 1 $ 個ずつこの順に刺さった串が最大何本作れるかを求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 1\ \leqq\ N\ \leqq\ 3\,000 $． - $ 1\ \leqq\ M\ \leqq\ 3\,000 $． ### 小課題 #### 小課題 1 \[13 点\] 以下の条件を満たす． - $ N\ \leqq\ 4 $． - $ M\ \leqq\ 4 $． #### 小課題 2 \[20 点\] 以下の条件を満たす． - $ N\ \leqq\ 10 $． - $ M\ \leqq\ 10 $． #### 小課題 3 \[67 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 次のように串に刺すことで，団子が刺さった串を $ 3 $ 本作ることができる． - 上から $ 1 $ 行目，左から $ 1 $ 列目の団子から右方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 1 $ 行目，左から $ 4 $ 列目の団子から下方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 3 $ 行目，左から $ 1 $ 列目の団子から右方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． $ 4 $ 本以上の串を作ることはできないので，$ 3 $ を出力する． - - - - - - ### Sample Explanation 2 次のように串に刺すことで，団子が刺さった串を $ 4 $ 本作ることができる． - 上から $ 1 $ 行目，左から $ 1 $ 列目の団子から右方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 1 $ 行目，左から $ 4 $ 列目の団子から下方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 2 $ 行目，左から $ 2 $ 列目の団子から下方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 2 $ 行目，左から $ 3 $ 列目の団子から下方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． $ 5 $ 本以上の串を作ることはできないので，$ 4 $ を出力する． - - - - - -