← 返回题目列表

AtCoder · tenka1_2018_e

E. 等边

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

里面有一些硬币 xy- 平面。 硬币的位置由字符网格表示 H 行和 W 列。 如果字符位于 i第行和 j第列, s_{ij}是 #,该点有一枚硬币 (i,j);如果该字符是 .,该点没有硬币 (i,j)。里面没有其他硬币 xy- 平面。

该点没有硬币 (x,y) 其中 1\leq i\leq H,1\leq j\leq W 不成立。 该点也没有硬币 (x,y) 其中 x or y (或两者)不是整数。 此外,两个或多个硬币永远不会存在于同一点。

找出满足以下条件的不同硬币的三元组的数量:

  • 选择三枚硬币中的任何两枚都会导致它们所在点之间的曼哈顿距离相同。

这里,点之间的曼哈顿距离 (x,y) 和 (x',y') is |x-x'|+|y-y'|。 如果两个三元组之间唯一的区别是硬币的顺序,则认为它们是相同的。

约束

  • 1 \leq H,W \leq 300
  • s_{ij} is # or ..

输入

输入由标准输入按以下格式给出:

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

输出

打印满足条件的三元组的数量。


示例输入 1

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

示例输出 1

3

((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)) 和 ((1,3),(3,1),(4,4)) 满足条件。


示例输入 2

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

示例输出 2

870