Problem:
 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

Solution (Python):
from itertools import accumulate

h, w = map(int, input().split())
field = [input() for _ in range(h)]

l = max(h, w)
precalc_rd = []
precalc_ld = []
for ij in range(h + w - 1):
    coins = [0] * (l + 1)
    min_i = max(0, ij - w + 1)
    max_i = ij - max(0, ij - h + 1)
    offset = (min_i - (ij - min_i) + w - 1) // 2 + 1
    for d in range(max_i - min_i + 1):
        i = min_i + d
        j = ij - i
        if field[i][j] == '
            coins[offset + d] = 1
    precalc_ld.append(list(accumulate(coins)))

for ij in range(-w + 1, h):
    coins = [0] * (l + 1)
    min_i = max(0, ij)
    max_i = ij + min(w - 1, h - ij - 1)
    offset = (min_i + (min_i - ij)) // 2 + 1
    for d in range(max_i - min_i + 1):
        i = min_i + d
        j = i - ij
        if field[i][j] == '
            coins[offset + d] = 1
    precalc_rd.append(list(accumulate(coins)))

ans = 0

for ij in range(h + w - 1):
    min_i = max(0, ij - w + 1)
    max_i = ij - max(0, ij - h + 1)
    offset = (min_i - (ij - min_i) + w - 1) // 2 + 1
    for sd in range(max_i - min_i + 1):
        si = min_i + sd
        sj = ij - si
        if field[si][sj] == '.':
            continue
        for td in range(sd + 1, max_i - min_i + 1):
            ti = min_i + td
            tj = ij - ti
            if field[ti][tj] == '.':
                continue
            dij = (td - sd) * 2
            if ij - dij >= 0:
                ans += precalc_ld[ij - dij][offset + td - 1] - precalc_ld[ij - dij][offset + sd - 1]
            if ij + dij <= h + w - 2:
                ans += precalc_ld[ij + dij][offset + td] - precalc_ld[ij + dij][offset + sd]

for ij in range(-w + 1, h):
    min_i = max(0, ij)
    max_i = ij + min(w - 1, h - ij - 1)
    offset = (min_i + (min_i - ij)) // 2 + 1
    for sd in range(max_i - min_i + 1):
        si = min_i + sd
        sj = si - ij
        if field[si][sj] == '.':
            continue
        for td in range(sd + 1, max_i - min_i + 1):
            ti = min_i + td
            tj = ti - ij
            if field[ti][tj] == '.':
                continue
            dij = (td - sd) * 2
            if ij - dij + w - 1 >= 0:
                ans += precalc_rd[ij - dij + w - 1][offset + td] - precalc_rd[ij - dij + w - 1][offset + sd]
            if ij + dij + w - 1 <= h + w - 2:
                ans += precalc_rd[ij + dij + w - 1][offset + td - 1] - precalc_rd[ij + dij + w - 1][offset + sd - 1]

print(ans)

Solution (Python):
H, W = map(int, input().split())
I = [input() for _ in range(H)]
X = [[[0, 1][a=="
k = 21
def r():
    global H, W, I
    I = ["".join([I[H - 1 - j][i] for j in range(H)]) for i in range(W)]
    H, W = W, H
def st1(s):
    return int(s.replace("
def st2(s):
    return int(s.replace("
def getsum(x):
    for i in range(8):
        x += x >> (k << i)
    return x & ((1 << k) - 1)

ans = 0
for _ in range(4):
    A1 = [st1(inp) for inp in I]
    A2 = [st1("".join([I[i][j] for i in range(H)])) for j in range(W)]
    B = [st2(inp[::-1]) for i, inp in enumerate(I)]
    for j in range(W):
        s, t = 0, 0
        m = (1 << j * k) - 1
        for i in range(H)[::-1]:
            s = ((B[i] >> (j + 1) * k) + (s << k)) & m
            t += A1[i] >> (W - j) * k & A2[j] >> (H - i) * k & s
        ans += getsum(t)
    r()
print(ans)

Solution (Python):
H, W = map(int, input().split())
I = [input() for _ in range(H)]
X = [[[0, 1][a=="
k = 32
def r():
    global H, W, I
    I = ["".join([I[H - 1 - j][i] for j in range(H)]) for i in range(W)]
    H, W = W, H
def st1(s):
    return int(s.replace("
def st2(s):
    return int(s.replace("
def getsum(x):
    for i in range(8):
        x += x >> (k << i)
    return x & ((1 << k) - 1)

ans = 0
for _ in range(4):
    A1 = [st1(inp) for inp in I]
    A2 = [st1("".join([I[i][j] for i in range(H)])) for j in range(W)]
    B = [st2(inp[::-1]) for i, inp in enumerate(I)]
    C = [[0] * W for _ in range(H)]
    for j in range(W):
        s = 0
        m = (1 << j * k) - 1
        for i in range(H)[::-1]:
            s <<= k
            s += B[i] >> (j+1) * k
            s &= m
            C[i][j] = s
    for i in range(1, H):
        for j in range(1, W):
            ans += A1[i] >> (W - j) * k & A2[j] >> (H - i) * k & C[i][j]
    r()
            
print(getsum(ans))

Solution (Python):
import sys
readline = sys.stdin.readline

H, W = map(int, readline().split())
G = [[0]*W for _ in range(H)]
L1 = [[0]*1000 for _ in range(W+H-1)]
geta1 = W-1
L2 = [[0]*1000 for _ in range(W+H-1)]
for i in range(H):
    S = [1 if s == '
    for j in range(W):
        G[i][j] = S[j]
        if S[j]:
            L1[i-j+geta1][i] = 1
            L2[i+j][i] = 1
for sub in range(W+H-1):
    for i in range(630):
        L1[sub][i] += L1[sub][i-1]
        L2[sub][i] += L2[sub][i-1]

res = 0
for su in range(2*max(H, W)+1):
    for w in range(max(0, su-H+1), min(W, su+1)):
        h = su-w
        if not G[h][w]:
            continue
        for k in range(1, min(h+1, W-w)):
            if not G[h-k][w+k]:
                continue
            idx1 = h+w-2*k
            if 0 <= idx1 < H+W-1:
                res += L2[idx1][h-k-1] - L2[idx1][h-2*k]
            idx2 = h+w+2*k
            if 0 <= idx2 < H+W-1:
                res += L2[idx2][h+k-1] - L2[idx2][h]

for mi in range(1-W, H):
    for w in range(max(0, -mi), min(W, H-mi)):
        h = mi + w
        if not G[h][w]:
            continue
        for k in range(1, min(H-h, W-w)):
            if not G[h+k][w+k]:
                continue
            idx1 = h-w-2*k + geta1
            if 0 <= idx1 < H+W-1:
                res += L1[idx1][h] - L1[idx1][h-k-1]
            idx2 = h-w+2*k + geta1
            if 0 <= idx2 < H+W-1:
                res += L1[idx2][h+2*k] - L1[idx2][h+k-1]

print(res)

Solution (Python):
import sys
input = sys.stdin.readline

class CumulativeSum2D:
    def __init__(self, field):
        self.h = len(field)
        self.w = len(field[0])
        self.h_offset = self.h
        self.w_offset = self.w
        self.field = field
        self.cumsum = [[0] * (self.w + self.w_offset * 2) for _ in range(self.h_offset)]
        for line in self.field:
            self.cumsum.append([0] * self.w_offset + line + [0] * self.w_offset)
        for i in range(self.h_offset):
            self.cumsum.append([0] * (self.w + self.w_offset * 2))
    
    def calc_diagonal_cumsum(self):
        
        for h in range(self.h_offset, self.h_offset + self.h):
            delta = 1
            while delta + h < self.h_offset * 2 + self.h and self.w_offset + delta < self.w_offset * 2 + self.w:
                self.cumsum[h + delta][self.w_offset + delta] += self.cumsum[h + delta-1][self.w_offset + delta-1]
                delta += 1
        for w in range(self.w_offset + 1, self.w_offset + self.w):
            delta = 1
            while delta + w < self.w_offset * 2 + self.w and self.h_offset + delta < self.h_offset * 2 + self.h:
                self.cumsum[self.h_offset + delta][w + delta] += self.cumsum[self.h_offset + delta - 1][w + delta - 1]
                delta += 1
    
    def get_diagonal_sum(self, x1, y1, x2, y2):
        ret = self.cumsum[y2 + self.h_offset][x2 + self.w_offset]
        ret -= self.cumsum[y1 - 1 + self.h_offset][x1 - 1 + self.w_offset]
        return ret

def rotate(field):
    h = len(field)
    w = len(field[0])
    h, w = w, h
    new_field = []
    for col in zip(*field):
        new_field.append(list(reversed(col)))
    return new_field

if __name__ == "__main__":
    n, m = [int(item) for item in input().split()]
    field = [[0] * m for _ in range(n)]
    for i in range(n):
        line = input().rstrip()
        for j in range(m):
            if line[j] == "
                field[i][j] = 1

    ans = 0
    for i in range(4):
        n = len(field)
        m = len(field[0])
        cs = CumulativeSum2D(field)
        cs.calc_diagonal_cumsum()
        lu_to_rd = [[] for _ in range(n + m - 1)]
        for i in range(m):
            x = i; y = 0
            delta = 0
            while x + delta < m and y + delta < n: 
                if field[y + delta][x + delta] == 1:
                    lu_to_rd[i].append((x + delta, y + delta))
                delta += 1
        for i in range(1, n):
            x = 0; y = i
            delta = 0
            while x + delta < m and y + delta < n:
                if field[y + delta][x + delta] == 1:
                    lu_to_rd[i + m - 1].append((x + delta, y + delta))
                delta += 1
        for line in lu_to_rd:
            length = len(line)
            if length <= 1:
                continue
            for i in range(length):
                for j in range(i+1, length):
                    x1, y1 = line[i]
                    x2, y2 = line[j]
                    d = abs(x1 - x2)
                    ans += cs.get_diagonal_sum(x1 + d + 1, y1 - d + 1, x2 + d, y2 - d)
        field = rotate(field)[:]
    print(ans)

Solution (Python):
import sys
b=sys.stdin.buffer
import numpy as np
H,W=map(int,b.readline().split());p=min(H,W)+1
S=np.pad((np.frombuffer(b.read(),dtype='S1')==b'
a=0
for _ in[0]*4:
  d=S[p:,p:].copy()
  for n in range(H+p):d[n,:W]+=d[n-1,1:W+1]
  for n in range(p):a+=(S[1+p:H+1+p,1-n+p:W+1-n+p]*S[1-n+p:H+1-n+p,1+p:W+1+p]*(d[1+n:H+1+n,1:W+1]-d[1:H+1,1+n:W+1+n])).sum()
  S = S.T[::-1,:];H,W=W,H
print(a)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

H,W = map(int,readline().split())
S = (np.frombuffer(read(),dtype='S1')==b'


p = min(H,W)+1

S = np.pad(S,(p,p),'constant')

def F(S,H,W):
    
    
    cnt = 0
    diag = np.zeros((H+p,W+p),np.int64)
    diag[:H,:W] += S[p:-p,p:-p]
    for n in range(1,H+p):
        diag[n,:W] += diag[n-1,1:W+1]
    for n in range(1,p):
        cnt += (S[1+p:H+1+p,1-n+p:W+1-n+p] * S[1-n+p:H+1-n+p,1+p:W+1+p] * (diag[1+n:H+1+n,1:W+1]-diag[1:H+1,1+n:W+1+n])).sum()
    return cnt

x = []
x.append(F(S,H,W))
S = S.T[::-1,:] 
x.append(F(S,W,H))
S = S.T[::-1,:] 
x.append(F(S,H,W))
S = S.T[::-1,:] 
x.append(F(S,W,H))

answer = sum(x)
print(answer)

Solution (Python):
H,W=map(int,input().split())
S=[input() for i in range(H)]
table=[[0]*(H+W-1) for i in range(H+W-1)]
for j in range(H):
    for i in range(W):
        if S[j][i]=='
            table[i+j][i-j+H-1]=1
yoko=[[0]*(H+W) for i in range(H+W-1)]
for j in range(H+W-1):
    for i in range(1,H+W):
            yoko[j][i]=yoko[j][i-1]+table[j][i-1]
tate=[[0]*(H+W-1) for i in range(H+W)]
for j in range(1,H+W):
    for i in range(H+W-1):
        tate[j][i]=tate[j-1][i]+table[j-1][i]

ans=0
for y in range(H+W-1):
    for x in range((y+H-1)%2,H+W-1,2):
        if table[y][x]!=1:
            continue
        for z in range(x+2,H+W-1,2):
            if table[y][z]==1:
                d=z-x
                if y+d<H+W-1:
                    ans+=yoko[y+d][z+1]-yoko[y+d][x]
                    
                if y-d>=0:
                    ans+=yoko[y-d][z+1]-yoko[y-d][x]
                    
        for w in range(y+2,H+W-1,2):
            if table[w][x]==1:
                e=w-y
                if x+e<H+W-1:
                    ans+=tate[w][x+e]-tate[y+1][x+e]
                    
                if x-e>=0:
                    ans+=tate[w][x-e]-tate[y+1][x-e]
                    

print(ans)

Solution (Python):
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
table=[[0]*(H+W-1) for i in range(H+W-1)]
for j in range(H):
    for i in range(W):
        if S[j][i]=='
            table[i+j][i-j+H-1]=1
yoko=[[0]*(H+W) for i in range(H+W-1)]
for j in range(H+W-1):
    for i in range(1,H+W):
            yoko[j][i]=yoko[j][i-1]+table[j][i-1]
tate=[[0]*(H+W-1) for i in range(H+W)]
for j in range(1,H+W):
    for i in range(H+W-1):
        tate[j][i]=tate[j-1][i]+table[j-1][i]

ans=0
for y in range(H+W-1):
    for x in range((y+H-1)%2,H+W-1,2):
        if table[y][x]!=1:
            continue
        for z in range(x+2,H+W-1,2):
            if table[y][z]==1:
                d=z-x
                if y+d<H+W-1:
                    ans+=yoko[y+d][z+1]-yoko[y+d][x]
                    
                if y-d>=0:
                    ans+=yoko[y-d][z+1]-yoko[y-d][x]
                    
        for w in range(y+2,H+W-1,2):
            if table[w][x]==1:
                e=w-y
                if x+e<H+W-1:
                    ans+=tate[w][x+e]-tate[y+1][x+e]
                    
                if x-e>=0:
                    ans+=tate[w][x-e]-tate[y+1][x-e]
                    

print(ans)

Solution (Python):
H,W=map(int,input().split())
S=[input() for i in range(H)]
table=[[0]*(H+W-1) for i in range(H+W-1)]
for j in range(H):
    for i in range(W):
        table[i+j][i-j+H-1]=S[j][i]
yoko=[[0]*(H+W) for i in range(H+W-1)]
for j in range(H+W-1):
    for i in range(1,H+W):
        if table[j][i-1]=='
            yoko[j][i]=yoko[j][i-1]+1
        else:
            yoko[j][i]=yoko[j][i-1]
tate=[[0]*(H+W-1) for i in range(H+W)]
for j in range(1,H+W):
    for i in range(H+W-1):
        if table[j-1][i]=='
            tate[j][i]=tate[j-1][i]+1
        else:
            tate[j][i]=tate[j-1][i]

ans=0
for y in range(H+W-1):
    for x in range((y+H-1)%2,H+W-1,2):
        if table[y][x]!='
            continue
        for z in range(x+2,H+W-1,2):
            if table[y][z]=='
                d=z-x
                if y+d<H+W-1:
                    ans+=yoko[y+d][z+1]-yoko[y+d][x]
                    
                if y-d>=0:
                    ans+=yoko[y-d][z+1]-yoko[y-d][x]
                    
        for w in range(y+2,H+W-1,2):
            if table[w][x]=='
                e=w-y
                if x+e<H+W-1:
                    ans+=tate[w][x+e]-tate[y+1][x+e]
                    
                if x-e>=0:
                    ans+=tate[w][x-e]-tate[y+1][x-e]
                    

print(ans)

Solution (Python):
H,W = map(int,input().split())
src = [input() for i in range(H)]

def solve():
    cums = [[0]*(H+W) for y in range(H+W-1)]
    coins = [[] for y in range(H+W-1)]
    for i in range(H):
        for j in range(W):
            if src[i][j] == '.': continue
            x,y = j-i+H, j+i
            cums[y][x] += 1
            coins[y].append(x)
    for i in range(H+W-1):
        for j in range(H+W-1):
            cums[i][j+1] += cums[i][j]
    cnt = 0
    for y1 in range(H+W-1):
        if len(coins[y1]) < 2: continue
        for i1 in range(len(coins[y1])-1):
            for i2 in range(i1+1,len(coins[y1])):
                x1,x2 = coins[y1][-1-i1], coins[y1][-1-i2]
                y2 = y1 - (x2 - x1)
                if y2 < 0: continue
                cnt += cums[y2][x2] - cums[y2][x1]
    return cnt

def rotate():
    global H,W,src
    H,W = W,H
    src2 = []
    for col in reversed(list(zip(*src))):
        src2.append(''.join(list(col)))
    src = src2

ans = 0
for i in range(4):
    rotate()
    ans += solve()
print(ans)

Solution (Python):
import itertools
import sys
H, W = [int(i) for i in input().split(' ')]

cross = [[0] * (H + W -1) for _ in range(H + W - 1)]
for i, line in enumerate(sys.stdin):
    for j, c in enumerate(line.strip()):
        if c == "
            cross[i+j][i-j+W-1] = 1

across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]

r = 0
for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[i][j] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[i][k] == 1:
                if i - (k-j) >= 0:
                    r += across[i - (k - j)][k+1] - across[i - (k - j)][j]
                if i + (k-j) < H + W - 1:
                    r += across[i + (k - j)][k+1] - across[i + (k - j)][j]

for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[j][i] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[k][i] == 1:
                if i - (k-j) >= 0:
                    r += across2[i - (k - j)][k] - across2[i - (k - j)][j+1]
                if i + (k-j) < H + W - 1:
                    r += across2[i + (k - j)][k] - across2[i + (k - j)][j+1]

print(r)

Solution (Python):





"""
tenka1-2018 E
"""

from itertools import product
from itertools import combinations

h, w = map(int, input().split())
slili = [list(input()) for i in range(h)]

coinsetli = [set() for i in range(h+w)]
for i, j in product(range(h), range(w)):
    if slili[i][j] == '
        coinsetli[i+j+1].add(j-i)

jmin = -304
jmin2 = jmin+2


coinacumdictli = [[] for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(jmin+tt, 303, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i].append(tmp)


coinacumdictli2 = [[] for i in range(h+w)]
for i in range(1, h+w):
    tt = (i % 2) - 1
    for j in range(len(coinacumdictli[i])-1):
        coinacumdictli2[i].append(coinacumdictli[i][j]+coinacumdictli[i][j+1])


coinlili = [[] for i in range(len(coinsetli))]
for i in range(len(coinsetli)):
    tt = (i % 2) - 1

    def rescale(x):
        return (x-jmin2-tt)//2
    coinlili[i] = sorted(list(map(rescale, coinsetli[i])))


ansdouble = 0
for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinlili[i], 2):
        j = 2*(y-x)
        imj = i-j
        ipj = i+j
        if imj >= 1:
            ansdouble += coinacumdictli2[imj][y] - coinacumdictli2[imj][x]
        if ipj <= h+w-1:
            ansdouble += coinacumdictli2[ipj][y] - coinacumdictli2[ipj][x]


for i in range(h):
    slili[i].reverse()

coinsetli = [set() for i in range(h+w)]
for i, j in product(range(h), range(w)):
    if slili[i][j] == '
        coinsetli[i+j+1].add(j-i)

jmin = -304
jmin2 = jmin+2

coinacumdictli = [[] for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(jmin+tt, 303, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i].append(tmp)


coinacumdictli2 = [[] for i in range(h+w)]
for i in range(1, h+w):
    tt = (i % 2) - 1
    for j in range(len(coinacumdictli[i])-1):
        coinacumdictli2[i].append(coinacumdictli[i][j]+coinacumdictli[i][j+1])

coinlili = [[] for i in range(len(coinsetli))]
for i in range(len(coinsetli)):
    tt = (i % 2) - 1

    def rescale(x):
        return (x-jmin2-tt)//2
    coinlili[i] = sorted(list(map(rescale, coinsetli[i])))


for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinlili[i], 2):
        j = 2*(y-x)
        imj = i-j
        ipj = i+j
        if imj >= 1:
            ansdouble += coinacumdictli2[imj][y] - coinacumdictli2[imj][x]
        if ipj <= h+w-1:
            ansdouble += coinacumdictli2[ipj][y] - coinacumdictli2[ipj][x]

print(ansdouble//2)

Solution (Python):

H, W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(list(input()))

res = 0

cross_posi = [[0]*(H+W-1) for _ in range(H+W-1)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "
            cross_posi[i+j][i-j+W-1] = 1
            

cross_posi_1 = [[0]*(H+W) for _ in range(H+W-1)]
for i in range(H+W-1):
    r = 0
    for j in range(H+W-1):
        r += cross_posi[i][j]
        cross_posi_1[i][j+1] = r
        
cross_posi_2 = [[0]*(H+W) for _ in range(H+W-1)]
for i in range(H+W-1):
    r = 0
    for j in range(H+W-1):
        r += cross_posi[j][i]
        cross_posi_2[i][j+1] = r

for s in range(H+W-1):
    for t in range((s+W+1)%2, H+W-2, 2):
        if cross_posi[s][t] == 1:
            for u in range(t+2, H+W-1, 2):
                if cross_posi[s][u] == 1:
                    d = (u - t)
                    if s >= d:
                        res += cross_posi_1[s-d][u+1] - cross_posi_1[s-d][t]
                    if s+d < H+W-1:
                        res += cross_posi_1[s+d][u+1] - cross_posi_1[s+d][t]
for s in range(H+W-1):
    for t in range((s+W+1)%2, H+W-2, 2):
        if cross_posi[t][s] == 1:
            for u in range(t+2, H+W-1, 2):
                if cross_posi[u][s] == 1:
                    d = (u - t)
                    if s >= d:
                        res += cross_posi_2[s-d][u] - cross_posi_2[s-d][t+1]
                    if s+d < H+W-1:
                        res += cross_posi_2[s+d][u] - cross_posi_2[s+d][t+1]
print(res)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W = reads()
S = []
for _ in range(H):
  S.append(input())

N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
  for j in range(W):
    field[i+j][i-j+W] = int(S[i][j] == '

accRow = [None] * N
for i in range(N):
  accRow[i] = [0] + list(accumulate(field[i][j] for j in range(N)))

accCol = [None] * N
for i in range(N):
  accCol[i] = [0] + list(accumulate(field[j][i] for j in range(N)))




ans = 0
for i in range(N):
  for j in range((i+W)%2, N, 2):
    for k in range(j+2, N, 2):
      d = k - j
      if field[i][j] == field[i][k] == 1:
        if i - d >= 0:
          ans += accRow[i-d][k+1] - accRow[i-d][j]
        if i + d < N:
          ans += accRow[i+d][k+1] - accRow[i+d][j]
      if field[j][i] == field[k][i] == 1:
        if i - d >= 0:
          ans += accCol[i-d][k] - accCol[i-d][j+1]
        if i + d < N:
          ans += accCol[i+d][k] - accCol[i+d][j+1]

print(ans)