Forest density

n, q = [int(x) for x in input().split()]

array = [[0 for _ in range(n)] for _ in range(n)]

for i in range(0, n):
    line = input()
    for j in range(0, n):
        if i != 0 and j != 0: array[i][j] = array[i-1][j] + array[i][j-1] - array[i-1][j-1]
        elif i != 0: array[i][j] = array[i-1][j]
        elif j != 0: array[i][j] = array[i][j-1]
        if line[j] == "*": array[i][j] += 1

# for line in array: print(line)

output = []
for i in range(q):
    coords = [int(x) - 1 for x in input().split()]
    answer = array[coords[2]][coords[3]]
    # print(answer)
    if coords[0] != 0: 
        # print(" 0 coords ", array[coords[0] - 1][coords[3]])
        answer -= array[coords[0] - 1][coords[3]]
    if coords[1] != 0: 
        # print("1 coord", array[coords[2]][coords[1] - 1])
        answer -= array[coords[2]][coords[1] - 1]
    if coords[1] != 0 and coords[0] != 0:
        answer += array[coords[0] - 1][coords[1]-1]
    output.append(str(answer))

print("\n".join(output))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED