Equilateral Triangles

题目描述

农夫约翰的牧场可以表示为一个 $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 \{50,75,100,125,150,175,200,225,250,275,300,300,300,300\}$。

有三头牛，它们构成一个等边三元组，因为每对牛之间的曼哈顿距离都等于二。

题目来源：Benjamin Qi

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum