Forest density

n, q = list(map(int, input().split()))
tab = []
for j in range(n):
    f = lambda x : 1 if x=="*" else 0
    row = list(map(f, input()))
    # print(row)
    tab.append(row)
# print("tab:", tab)
dp = [[0]*n]
# dp[0] = tab[0].copy()
sum_line=0
for j in range(n):
    sum_line+= tab[0][j]
    dp[0][j]=sum_line
# print(dp)
for i in range(1,n):
    new_row = [0]*n
    sum_line = 0
    for j in range(n):
        sum_line += tab[i][j]
        # print(sum_line)
        new_row[j] = dp[i-1][j]+sum_line
    dp.append(new_row)

# print(dp)
for query in range(q):
    i1, j1, i2, j2 = list(map(int, input().split()))
    rec = dp[i2-1][j2-1]
    # print(rec)
    if i1>=2 : rec -= dp[i1-2][j2-1]
    if j1>=2 : rec -= dp[i2-1][j1-2]
    if i1 >= 2 and j1>=2:
        rec += dp[i1-2][j1-2]
    print(rec)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED