<p>Given a <code>matrix</code>&nbsp;and a <code>target</code>, return the number of non-empty submatrices that sum to <font face="monospace">target</font>.</p>

<p>A submatrix <code>x1, y1, x2, y2</code> is the set of all cells <code>matrix[x][y]</code> with <code>x1 &lt;= x &lt;= x2</code> and <code>y1 &lt;= y &lt;= y2</code>.</p>

<p>Two submatrices <code>(x1, y1, x2, y2)</code> and <code>(x1&#39;, y1&#39;, x2&#39;, y2&#39;)</code> are different if they have some coordinate&nbsp;that is different: for example, if <code>x1 != x1&#39;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/02/mate1.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
<strong>Output:</strong> 4
<strong>Explanation:</strong> The four 1x1 submatrices that only contain 0.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[1,-1],[-1,1]], target = 0
<strong>Output:</strong> 5
<strong>Explanation:</strong> The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[904]], target = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= matrix.length &lt;= 100</code></li>
	<li><code>1 &lt;= matrix[0].length &lt;= 100</code></li>
	<li><code>-1000 &lt;= matrix[i][j] &lt;= 1000</code></li>
	<li><code>-10^8 &lt;= target &lt;= 10^8</code></li>
</ul>

class Solution {
    int vm[100][100] = {0};
public:
    Solution() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    }

// int vm[100][100] = {0};

inline int ar(const int &r, const int &c) {
    if (r < 0 || c < 0)
        return 0;

    return vm[r][c];
}

int getArea(const int &r1, const int &c1, const int &r2, const int &c2) {
    return ar(r1 - 1, c1 - 1) + ar(r2, c2) - ar(r1 - 1, c2) - ar(r2, c1 - 1);
}

int numSubmatrixSumTarget(const vector<vector<int>> &matrix, const int &target) {
    const int rows = matrix.size();
    const int cols = matrix[0].size();
    int sum = 0;

    // vector<vector<int>> vm =
    //     vector<vector<int>>(rows, vector<int>(cols, 0));
    vm[0][0] = matrix[0][0];

    for (int i = 1; i < rows; i++)
        vm[i][0] = vm[i - 1][0] + matrix[i][0];

    for (int i = 1; i < cols; i++)
        vm[0][i] = vm[0][i - 1] + matrix[0][i];

    for (int r = 1; r < rows; r++)
        for (int c = 1; c < cols; c++)
            vm[r][c] = vm[r - 1][c] + vm[r][c - 1] - vm[r - 1][c - 1] + matrix[r][c];

    unordered_map<int, int> um;
    um.reserve(cols);

    for (int r1 = 0; r1 < rows; r1++)
        for (int r2 = r1; r2 < rows; r2++) {
            um.clear();
            um[0]++;
            for (int c1 = 0; c1 < cols; c1++) {
                const int area = getArea(r1, 0, r2, c1);
                if (um.count(area - target))
                    sum += um.at(area - target);
                um[area]++;
            }
        }

    return sum;
}
};
67005