3369. [USACO20 Feb Platinum]Equilateral Triangles

【题目描述】

Farmer John 的牧场可以被表示为一个 $N\times N$ 的正方形方阵（$1\le N\le 300$），包含 $1\le i,j\le N$ 内的所有位置 $(i,j)$。对于方阵内的每个方格，如果在这个位置上有一头奶牛，输入中对应的字符为 '*'，如果这个位置没有奶牛则为 '.'。

FJ 相信他的牧场的美丽程度正比于两两距离相等的奶牛三元组的数量。也就是说，她们组成一个等边三角形。不幸的是，直到最近 FJ 才发现，由于他的奶牛都处在整数坐标位置，如果使用欧几里得距离进行计算，不可能存在美丽的奶牛三元组！于是，FJ 决定改用“曼哈顿”距离。形式化地说，两点 $(x_0,y_0)$ 和 $(x_1,y_1)$ 之间的曼哈顿距离等于 $|x_0-x_1|+|y_0-y_1|$。

给定表示奶牛位置的方阵，计算等边三角形的数量。

【输入格式】

第一行包含一个整数 $N$。

对于每个 $1\le i\le N$，第 $i+1$ 行包含一个长为 $N$ 的仅由字符 '*' 和 '.' 组成的字符串。第 $j$ 个字符描述了是否在位置 $(i,j)$ 存在一头奶牛。

【输出格式】

输出一个整数，为所求的答案。可以证明答案可以用 32 位有符号整数型存储。

【样例输入】

3
*..
.*.
*..

【样例输出】

1

【样例解释】

有三头奶牛，并且她们组成了一个等边三角形，因为每对奶牛之间的曼哈顿距离都等于二。

【提示】

对于每个测试点，依次满足 $N\in \{3,50,75,100,125,150,175,200,225,250,275,300,300,300,300\}$。

【来源】

USACO 二月公开赛 Platinum 组