Forest density

def forest_density(n,q,forest,barr):

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

    
    for i in range(1, n + 1):

        for j in range(1, n + 1):

            prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]

            if forest[i-1][j-1] == '*':
                prefix_sum[i][j] += 1

    for y1, x1, y2, x2 in barr:
        result = prefix_sum[y2][x2] - prefix_sum[y1-1][x2] - prefix_sum[y2][x1-1] + prefix_sum[y1-1][x1-1]
        print(result)


n, q = map(int, input().split())
forest = [input().strip() for _ in range(n)]

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

forest_density(n,q,forest,barr)

# Input:
# 4 3
# .*..
# *.**
# **..
# ****
# 2 2 3 4
# 3 1 3 1
# 1 1 2 2
# Output:
# 3
# 1
# 2

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED