Forest density

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    vector<string> forest(n);
    for (int i = 0; i < n; ++i) {
        cin >> forest[i];
    }

    vector<vector<int>> pre(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (forest[i-1][j-1] == '*')
                pre[i][j] = 1 + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
            else 
                pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
        }
    }

   for (int i = 0; i < q; ++i) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        int result = pre[y2][x2] - pre[y1-1][x2] - pre[y2][x1-1] + pre[y1-1][x1-1];
        cout << result << endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED