Gold Mines

There is a rectangular grid of gold mines. The grid has R rows and C columns. So it has R*C cells in total. The rows are numbered from 1 to R and the columns are numbered from 1 to C. The topmost row has number 1, the row next to it has number 2, and so on. Similarly, the leftmost column has number 1, the column next to it has number 2, and so on. Each cell in the grid has a unique coordinate which is (x, y) where x is the row number and y is the column number of that particular cell.

Each cell in the grid has a certain amount of gold in it. Total gold in a sub rectangle of the grid is the sum of all units of gold contained in the cells that are inside the rectangle. Your task is to find the total gold in the given sub rectangle.

A sub rectangle of the grid is defined by four integers x1, y1, x2 and y2. A cell (x, y) belongs to the sub rectangle if and only if x1 <= x <= x2 and y1 <= y <=y2

Example:

Input: r = 4, c = 4, mat = {{2, 8, 9, 7}, {5, 8, 1, 7}, {5, 7, 3, 5}, {4, 8, 7, 4}}, q = 4, queries = {{1, 2, 4, 2}, {1, 4, 2, 4}, {1, 1, 4, 2}, {2, 4, 2, 4}}

Output:

31
14
-7543601
7

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

void goldMines(long r, long c, vector<vector<long>> mat,
               long q, vector<vector<long>> queries)

{
    long dp[r + 1][c + 1] = {0};
    for (long i = 1; i <= r; i++)
    {
        long temp = 0;
        for (long j = 1; j <= c; j++)
        {
            temp += mat[i - 1][j - 1];
            dp[i][j] = temp;
        }
    }
    for (long i = 1; i <= r; i++)
    {
        for (long j = 1; j <= c; j++)
            dp[i][j] += dp[i - 1][j];
    }
    for (long i = 0; i < q; i++)
    {
        long x1 = queries[i][0];
        long y1 = queries[i][1];
        long x2 = queries[i][2];
        long y2 = queries[i][3];

        cout << dp[x2][y2] - dp[x1 - 1][y2] - 
        dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << "\n";
    }
}
int main()
{

    long r = 4, c = 4;

    vector<vector<long>> mat = {{2, 8, 9, 7},
                                {5, 8, 1, 7},
                                {5, 7, 3, 5},
                                {4, 8, 7, 4}};
    long q = 4;

    vector<vector<long>> queries = {{1, 2, 4, 2},
                                    {1, 4, 2, 4},
                                    {1, 1, 4, 2},
                                    {2, 4, 2, 4}};

    goldMines(r, c, mat, q, queries);

    return 0;
}