C - 団子職人 (Dango Maker)
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点： 100 点
あなたは団子を作る職人である．今，あなたは団子に串を刺そうとしているところである．
団子は，縦 N 行，横 M 列に仕切られたマスの中に配置されている．各マスには団子が 1 個ずつ入っている．それぞれの団子には，赤 (R)，緑 (G)，白 (W) のいずれかの色が付いている．あなたは，左から右の方向，または，上から下の方向に連続する 3 マスから団子を取り出し，この順に 1 本の串にちょうど 3 個刺すことができる．
今あなたは，赤，緑，白の団子が 1 個ずつこの順に刺さった串を可能な限り多く作りたい．串に刺す順番は，マスから取り出した順番と同じでなければならない．また，同じ団子に 2 本以上の串を刺すことはできない．
あなたは，団子が刺さった串を最大何本作ることができるだろうか．
課題
マスの中に配置された団子の色の情報が与えられたとき，赤，緑，白の団子が 1 個ずつこの順に刺さった串が最大何本作れるかを求めるプログラムを作成せよ．
入力
標準入力から以下の入力を読み込め．
- 1 行目には，整数 N と M が空白を区切りとして書かれている．
- 続く N 行のうちの i 行目 (1 \leqq i \leqq N) には，
R,G,Wからなる長さ M の文字列が書かれている．この文字列の j 文字目 (1 \leqq j \leqq M) は，上から i 行目，左から j 列目のマスの団子の色を表す．
出力
標準出力に，団子が刺さった串の本数の最大値を 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 点]
追加の制限はない．
入力例 1
3 4 RGWR GRGG RGWW
出力例 1
3
次のように串に刺すことで，団子が刺さった串を 3 本作ることができる．
- 上から 1 行目，左から 1 列目の団子から右方向に 3 個の団子を取り出し，この順に串に刺す．
- 上から 1 行目，左から 4 列目の団子から下方向に 3 個の団子を取り出し，この順に串に刺す．
- 上から 3 行目，左から 1 列目の団子から右方向に 3 個の団子を取り出し，この順に串に刺す．
4 本以上の串を作ることはできないので，3 を出力する．
入力例 2
4 4 RGWR GRRG WGGW WWWR
出力例 2
4
次のように串に刺すことで，団子が刺さった串を 4 本作ることができる．
- 上から 1 行目，左から 1 列目の団子から右方向に 3 個の団子を取り出し，この順に串に刺す．
- 上から 1 行目，左から 4 列目の団子から下方向に 3 個の団子を取り出し，この順に串に刺す．
- 上から 2 行目，左から 2 列目の団子から下方向に 3 個の団子を取り出し，この順に串に刺す．
- 上から 2 行目，左から 3 列目の団子から下方向に 3 個の団子を取り出し，この順に串に刺す．
5 本以上の串を作ることはできないので，4 を出力する．
入力例 3
5 5 RGRGW GRRGW WGGWR RWRGW RGWGW
出力例 3
6