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