#P7465. [CERC2018] Matrice

[CERC2018] Matrice

题目描述

译自 [CERC2018] Matrice

特工 Sue Thomas 和她的儿子正在网格中寻找 trinity。trinity 是一个新词,正如词素 tri 所示,指的是由网格中单元格组成的三角形。

每个 trinity 是一个正方形的单元格区域去除某对角线上方或下方的部分(一个等腰直角三角形,两腰分别与网格两边分别平行)。对角线可以是主对角线(东南-西北方向),也可以是副对角线(西南-东北方向)。一个合法的 trinity 至少包含三个单元格,并且所有单元格中字符都相同。

输入格式

输入的第一行是两个整数 N,MN,M,分别表示这个网格的行数和列数。

接下来 NN 行每行一个长为 MM 的字符串,表示这个网格。

输出格式

输出网格中所有不同合法的 trinity 个数。

2 2
AA
Ad
1
5 5
#####
####.
###..
##...
#....
60
5 4
hwwr
eahe
lroy
lswo
oaau
0
5 6
#girls
##areb
#.#est
#..#!!
#####!
7

提示

1N,m1031≤N,m≤10^3,保证输入中出现的字符 ASCII 码在 3333126126 之间。