Forest density

def main():
    n, q = map(int, input().split())

    forest = [list(map(str, input())) for _ in range(n)]
    commands = [list(map(int, input().split())) for _ in range(q)]
    for i in range(n):
        for j in range(n):
            if forest[i][j] == "*":
                forest[i][j] = 1
            else:
                forest[i][j] = 0
    prefix = [[0]*(n+1) for _ in range(n+1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            prefix[i][j] = prefix[i][j - 1] + prefix[i - 1][j] + forest[i - 1][j - 1] - prefix[i - 1][j - 1]


    for command in commands:
        y1, x1, y2, x2 = command
        res = prefix[y2][x2] - prefix[y2][x1-1] - prefix[y1-1][x2] + prefix[y1-1][x1-1]
        print(res)




if __name__ == "__main__":
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED