Forest density

n, q = map(int, input().split())

forest = [[] for _ in range(n)]
for y in range(n):
    row = input().strip()
    row_trees = 0
    for x, c in enumerate(row):
        if c == "*":
            row_trees += 1
        temp = row_trees
        if y != 0:
            temp += forest[y-1][x]
        forest[y].append(temp)

def get_value(arr: list, y: int, x: int):
    if y < 0 or x < 0:
        return 0
    return arr[y][x]

for _ in range(q):
    y1, x1, y2, x2 = map(lambda x: int(x) - 1, input().split())
    A = get_value(forest, y2, x2)
    B = get_value(forest, y2, x1-1)
    C = get_value(forest, y1-1, x2)
    D = get_value(forest, y1-1, x1-1)
    count = A - B - C + D
    print(count)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED