問題文
H 行 W 列组成的网格。从上面 i 行,从左起 j 标记列中的方块
表示为 (i,j) 。在每个方格内
如果写入任何字符 E, F, G , (i,j) 中写入的字符是给定的字符串 S_i 的
合并 j 与第一个字符相同。
满足以下所有条件 3 方块组 查找 (r_1,c_1),(r_2,c_2),(r_3,c_3) 的编号。
- 1\le r_1 < r_2 < r_3 \le H
- 1\le c_{\color{red}1\color{black}} < c_{\color{red}3\color{black}}<c_{\color{red}2\color{black}} \le W
- 质量 (r_1,c_1) 中写入的字符是
E - 质量 (r_2,c_2) 中写入的字符是
F - 质量 (r_3,c_3) 中写入的字符是
G
制約
- 3\le H,W\le 2000
- H,W 是一个整数 长度由
- S_i 是
E,F,G组成 W 字符串
入力
输入是按以下格式从标准输入给出的。
H W S_1 S_2 \vdots S_H
出力
满足所有条件 3 打印方块组数。此外,在该问题的约束下,答案为 64 bit 可以证明它落在有符号整数类型的范围内。 只有
入力例 1
3 3 EGF EGF EGF
出力例 1
1
(r_1,c_1)=(1,1),(r_2,c_2)=(2,3),(r_3,c_3)=(3,2) 满足条件。
入力例 2
3 4 GGGG FFFF EEEE
出力例 2
0
满足所有条件 3 正方形集合不存在。
入力例 3
7 5 FEGFG FFEEF EEFFG GFEGE GGEEG GEGFE GFFGF
出力例 3
4