Forest density

def main():
    n, q = [int(x) for x in input().split()]

    pref = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        row = input().strip()
        for j in range(1, n + 1):
            val = 1 if row[j - 1] == "*" else 0
            pref[i][j] = val + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1]

    for _ in range(q):
        area = [int(x) for x in input().split()]
        y1, x1, y2, x2 = area

        res = pref[y2][x2] - pref[y1 - 1][x2] - pref[y2][x1 - 1] + pref[y1 - 1][x1 - 1]

        print(res)


main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED