配点 : $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}$

出力

条件を満たす組の個数を出力せよ。

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

3

$((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)),((1,3),(3,1),(4,4))$ が条件を満たします。

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

870