← 返回题目列表

AtCoder · guildfes_2026_final_g

G. EGF 网格

中文机器翻译题面 查看原题

問題文

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