题目描述

$xy$ 平面上にコインがいくつかあります。 コインの配置は $H$ 行 $W$ 列のグリッドを用いて表され、グリッドの $i$ 行 $j$ 列目の文字 $s_{ij}$ が # のとき座標 $(i,j)$ にコインがひとつあることを、 . のとき座標 $(i,j)$ にコインがないことを表します。 その他に $xy$ 平面上にコインは存在しません。

相異なるコインの $3$ つ組であって、以下の条件を満たすものの個数を求めてください。

• $3$ つのうちどの $2$ つのコインをとっても、それらの存在する座標の間のマンハッタン距離が一定である

ただし、座標 $(x,y),(x',y')$ の間のマンハッタン距離は、$|x-x'|+|y-y'|$ で表されます。 また、コインの順番を入れ替えただけの組は同じものとみなします。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $s_{11}...s_{1W}$ $:$ $s_{H1}...s_{HW}$

输出格式

条件を満たす組の個数を出力せよ。

题目大意

给定一个 $N\times M(N,M\leq300)$ ，仅包含 # 和 . 的字符矩阵 $a$ 。

求满足以下条件的坐标三元组 $((x_1,y_1),(x_2,y_2),(x_3,y_3))$ 的数量：

• $a_{x_1,y_1}=a_{x_2,y_2}=a_{x_3,y_3}=$ #
• $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ 三点之间的曼哈顿距离两两相等。

5 4
#.##
.##.
#...
..##
...#

3

13 27
......#.........#.......#..
#############...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
#############.#.#.#...###..
#...........#...#...#######
#..#######..#...#...#.....#
#..#.....#..#...#...#.###.#
#..#######..#...#...#.#.#.#
#..........##...#...#.#####

870

提示

制約

• $1\ \leq\ H,W\ \leq\ 300$
• $s_{ij}$ は # または . である

Sample Explanation 1

$((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)),((1,3),(3,1),(4,4))$ が条件を満たします。