Forest density

n, q = map(int, input().split())
 
# Create grid and prefix sum array
forest = [list(input()) for i in range(n)]
 
# print("forest:", forest)
 
# Prefix sum array
prefix = [[0] * (n + 1) for _ in range(n + 1)]
 
# print("prefix:", prefix)
 
# Build prefix sum array
for i in range(1, n + 1):
    for j in range(1, n + 1):
        # Check if there is a tree
        tree = 1 if forest[i - 1][j - 1] == "*" else 0
        prefix[i][j] = tree + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]
 
# Process queries
results = []
for i in range(q):
    y1, x1, y2, x2 = map(int, input().split())
    # Inclusion-exclusion principle to get the num of trees in rectangle
    result = (prefix[y2][x2]
              - prefix[y1 - 1][x2]
              - prefix[y2][x1 - 1]
              + prefix[y1 - 1][x1 - 1])
    results.append(result)
 
# Output all the results at once
print("\n".join(map(str, results)))
 

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED