\((r_2,c_3)\) のペアを全探索することを考えます。このペアを固定した際に \(r_1,c_1,r_3,c_2\) としてあり得るものの個数を求めることを考えます。

まず、\((r_1,c_1)\) としてあり得るマスの個数はマス \((r_2,c_2)\) より左上にある E の個数と同じです。同様に、\((r_2,c_2)\) としてあり得るマスの個数はマス \((r_2,c_2)\) より右にある F の個数と同じで、\((r_3,c_3)\) としてあり得るマスの個数はマス \((r_2,c_2)\) より下にある G の個数と同じです。

これらの個数は累積和・二次元累積和を前計算しておくことで高速に計算することができます。計算量は \(O(HW)\) です。

実装例(Python3)

h, w = map(int, input().split())
s = [input() for _ in range(h)]
e = [[0] * w for _ in range(h)]
f = [[0] * w for _ in range(h)]
g = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        e[i][j] += s[i][j] == "E"
        f[i][j] += s[i][j] == "F"
        g[i][j] += s[i][j] == "G"
for i in range(h - 1):
    for j in range(w):
        e[i + 1][j] += e[i][j]
for i in range(h):
    for j in range(w - 1):
        e[i][j + 1] += e[i][j]
for i in range(h):
    for j in range(w - 1, 1, -1):
        f[i][j - 1] += f[i][j]
for i in range(h - 1, 1, -1):
    for j in range(w):
        g[i - 1][j] += g[i][j]
ans = 0
for i in range(1, h - 1):
    for j in range(1, w - 1):
        ans += e[i - 1][j - 1] * f[i][j + 1] * g[i + 1][j]
print(ans)