Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
xy 平面上にコインがいくつかあります。
コインの配置は H 行 W 列のグリッドを用いて表され、グリッドの i 行 j 列目の文字 s_{ij} が #
のとき座標 (i,j) にコインがひとつあることを、
.
のとき座標 (i,j) にコインがないことを表します。
その他に xy 平面上にコインは存在しません。
相異なるコインの 3 つ組であって、以下の条件を満たすものの個数を求めてください。
- 3 つのうちどの 2 つのコインをとっても、それらの存在する座標の間のマンハッタン距離が一定である
ただし、座標 (x,y),(x',y') の間のマンハッタン距離は、|x-x'|+|y-y'| で表されます。 また、コインの順番を入れ替えただけの組は同じものとみなします。
制約
- 1 \leq H,W \leq 300
- s_{ij} は
#
または.
である
入力
入力は以下の形式で標準入力から与えられる。
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
Score : 700 points
Problem Statement
There are some coins in the xy-plane.
The positions of the coins are represented by a grid of characters with H rows and W columns.
If the character at the i-th row and j-th column, s_{ij}, is #
, there is one coin at point (i,j); if that character is .
, there is no coin at point (i,j). There are no other coins in the xy-plane.
There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not hold. There is also no coin at point (x,y) where x or y (or both) is not an integer. Additionally, two or more coins never exist at the same point.
Find the number of triples of different coins that satisfy the following condition:
- Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.
Here, the Manhattan distance between points (x,y) and (x',y') is |x-x'|+|y-y'|. Two triples are considered the same if the only difference between them is the order of the coins.
Constraints
- 1 \leq H,W \leq 300
- s_{ij} is
#
or.
.
Input
Input is given from Standard Input in the following format:
H W s_{11}...s_{1W} : s_{H1}...s_{HW}
Output
Print the number of triples that satisfy the condition.
Sample Input 1
5 4 #.## .##. #... ..## ...#
Sample Output 1
3
((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)) and ((1,3),(3,1),(4,4)) satisfy the condition.
Sample Input 2
13 27 ......#.........#.......#.. #############...#.....###.. ..............#####...##... ...#######......#...####### ...#.....#.....###...#...#. ...#######....#.#.#.#.###.# ..............#.#.#...#.#.. #############.#.#.#...###.. #...........#...#...####### #..#######..#...#...#.....# #..#.....#..#...#...#.###.# #..#######..#...#...#.#.#.# #..........##...#...#.#####
Sample Output 2
870