Forest density

n, q = map(int, input().split())
x = [[0] * (n + 1) for _ in range(n + 1)]

line = input()
for j in range(1, n + 1):
    if line[j - 1] == '*':
        x[1][j] = x[1][j - 1] + 1
    else:
        x[1][j] = x[1][j - 1]

for i in range(2, n + 1):
    line = input()
    for j in range(1, n + 1):
        x[i][j] = x[i][j - 1] + x[i - 1][j] - x[i - 1][j - 1]
        if line[j - 1] == '*':
            x[i][j] += 1


for i in range(q):
    a, b, c, d = map(int, input().split())
    print(x[c][d] - x[a - 1][d] - x[c][b - 1] + x[a - 1][b - 1])

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED