#2349. 「JOI 2018 Final」团子制作

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

你是一个制作团子的师傅,现在,你正想用竹签把团子串成一串。

团子被放置在长为 N 行,宽为 M 列的隔开的格子里,每个格子里都放着一个团子。每个团子的颜色是红、绿与白中的一种。

你可以选择三个从左到右,或者从上到下的连续的格子,把格子中的团子串成一串,按照这个顺序,一串团子串上正好会有三个团子。

现在,你希望尽可能多做些颜色按照红绿白顺序的团子串,并且团子在串上的顺序必须与从格子中取出的顺序相同。需要注意的是,同一个团子只能被串在一串团子串上。

你最多能制作多少串团子串呢?

给出放置在每个格子上的团子的颜色,你需要计算最多能制作的团子串的数量。团子串的颜色必须按照红、绿、白的顺序。

输入格式

从标准输入中读取数据。

第一行包括两个整数 N, M

接下来 N 行,第 i+1 行有长为 M 的字符串,其字符集为 R, G, W。第 j 个字符表示第 i 行第 j 列放置的团子的颜色。

输出格式

输出数据到标准输出中。

输出一行一个整数,表示最多能串成团子串的数量。

样例

样例输入 1
3 4
RGWR
GRGG
RGWW
样例输出 1
3
样例说明 1

样例中所串成的三串团子串分别为:

第一串:第一行第一列开始,从左往右三个格子上放置的团子。
第二串:第一行第四列开始,从上往下三个格子上放置的团子。
第三串:第三行第一列开始,从左往右三个格子上放置的团子。

样例输入 2
4 4
RGWR
GRRG
WGGW
WWWR
样例输出 2
4
样例说明 2

样例中所串成的四串团子串分别为:

第一串:第一行第一列开始,从左往右三个格子上放置的团子。
第二串:第一行第四列开始,从上往下三个格子上放置的团子。
第三串:第二行第二列开始,从上往下三个格子上放置的团子。
第四串:第二行第三列开始,从上往下三个格子上放置的团子。

样例输入 3
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
样例输出 3
6

数据范围与提示

Subtask # 分值 N, M
1 13 N, M\le 4
2 20 N, M\le 10
3 67 N, M\le 3000