Equilateral Triangles
提交数: 5, 通过率: 0%, 平均分: 13.2
题目描述:
Farmer John 的牧场可以被表示为一个 N×N 的正方形方阵（1≤N≤300），包含 1≤i,j≤N 内的所有位置(i,j)。对于方阵内的每个方格，如果在这个位置上有一头奶牛，输入中对应的字符为 '*'，如果这个位置没有奶牛则为 '.'。
FJ 相信他的牧场的美丽程度正比于两两距离相等的奶牛三元组的数量。也就是说，她们组成一个等边三角形。不幸的是，直到最近 FJ 才发现，由于他的奶牛都处在整数坐标位置，如果使用欧几里得距离进行计算，不可能存在美丽的奶牛三元组！于是，FJ 决定改用“曼哈顿”距离。形式化地说，两点 (x0,y0) 和 (x1,y1) 之间的曼哈顿距离等于 |x0−x1|+|y0−y1|。
给定表示奶牛位置的方阵，计算等边三角形的数量。
测试点性质： 除了样例之外有十四个测试点，依次满足 N∈{50,75,100,125,150,175,200,225,250,275,300,300,300,300}。
输入格式:
第一行包含一个整数 NN。
对于每个 1≤i≤N，第 i+1 行包含一个长为 N 的仅由字符 '*' 和 '.' 组成的字符串。第 j 个字符描述了是否在位置 (i,j) 存在一头奶牛。
输出格式:
输出一个整数，为所求的答案。可以证明答案可以用 32 位有符号整数型存储。
样例输入:
3 *.. .*. *..
样例输出:
1
提示:
有三头奶牛，并且她们组成了一个等边三角形，因为每对奶牛之间的曼哈顿距离都等于二。
时间限制: 1000ms空间限制: 256MB
来源: USACO 2020 FEB Platinum