[AdditionalFile6556.zip](file://AdditionalFile6556.zip?type=additional_file)

#6556. 「CERC2018」Matrice

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 CERC 2018「J. Matrice」

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

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

输入格式

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

接下来 $N$ 行每行一个长为 $M$ 的字符串，表示这个网格。

输出格式

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

样例 1

输入

2 2
AA
Ad

输出

1

样例 2

输入

5 5
#####
####.
###..
##...
#....

输出

60

样例 3

输入

5 4
hwwr
eahe
lroy
lswo
oaau

输出

0

样例 4

输入

5 6
#girls
##areb
#.#est
#..#!!
#####!

输出

7

数据范围与提示

$1\le N,M\le 10^3$，保证输入中出现的字符 ASCII 码在 $33$ 到 $126$ 之间。