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