leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0304.cpp (854B)

      1 class NumMatrix {
      2     int n, m;
      3     vector<vector<int>> dp;
      4 
      5   public:
      6     NumMatrix(vector<vector<int>> &matrix)
      7         : n(matrix.size()), m(matrix[0].size()), dp(vector<vector<int>>(n, vector<int>(m, 0))) {
      8         for (int i = 0, sum = 0; i < n; i++)
      9             sum = dp[i][0] = matrix[i][0] + sum;
     10         for (int i = 0, sum = 0; i < m; i++)
     11             sum = dp[0][i] = matrix[0][i] + sum;
     12         for (int i = 1; i < n; i++) {
     13             for (int j = 1; j < m; j++) {
     14                 dp[i][j] = matrix[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
     15             }
     16         }
     17     }
     18 
     19     int sumRegion(int x1, int y1, int x2, int y2) {
     20         int res = dp[x2][y2];
     21         if (x1 > 0) res -= dp[x1 - 1][y2];
     22         if (y1 > 0) res -= dp[x2][y1 - 1];
     23         if (x1 > 0 && y1 > 0) res += dp[x1 - 1][y1 - 1];
     24         return res;
     25     }
     26 };