Forest density

n, q = [int(x) for x in input().split()]
queries = []
forest = []
for _ in range(n):
    forest.append(list(input()))
 
sum_forest = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        sum_forest[i][j] = (1 if forest[i][j] == '*' else 0)
        if i > 0:
            sum_forest[i][j] += sum_forest[i-1][j]
        if j > 0:
            sum_forest[i][j] += sum_forest[i][j-1]
        if i > 0 and j > 0:
            sum_forest[i][j] -= sum_forest[i-1][j-1]
 
for _ in range(q):
    y1, x1, y2, x2 = [int(x)-1 for x in input().split()]
    result = sum_forest[y2][x2]
    if y1 > 0:
        result -= sum_forest[y1-1][x2]
    if x1 > 0:
        result -= sum_forest[y2][x1-1]
    if y1 > 0 and x1 > 0:
        result += sum_forest[y1-1][x1-1]
    queries.append(result)
 
for query in queries:
    print(query)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED