C ++中的矩阵块总和

假设我们有一个名为mat的m * n矩阵和一个整数K,我们必须找到另一个矩阵答案,其中每个答案[i] [j]是i-K <=的所有元素mat [r] [c]的总和r <= i + K,j-K <= c <= j + K,并且(r,c)是矩阵中的有效位置。所以如果输入像-

123
456
789

且k为1,则输出为-

122116
274533
243928

为了解决这个问题,我们将遵循以下步骤-

  • n:=行数,m =列数

  • 定义一个矩阵ans,其顺序为nxm

  • 对于i,范围为0至n – 1

    • 对于在i – k到i + k范围内的r

    • 如果r和c在矩阵索引内,则

    • ans [i,j]:= ans [i,j] + mat [r,c]

    • 对于范围j – k至j + k的c

    • 对于j,范围从0到m – 1

    • 返回ans

    例子(C ++)

    让我们看下面的实现以更好地理解-

    #include <bits/stdc++.h>
    using namespace std;
    void print_vector(vector<vector<auto> > v){
       cout << "[";
       for(int i = 0; i<v.size(); i++){
          cout << "[";
          for(int j = 0; j <v[i].size(); j++){
             cout << v[i][j] << ", ";
          }
          cout << "],";
       }
       cout << "]"<<endl;
    }
    class Solution {
    public:
       vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
          int n = mat.size();
          int m = mat[0].size();
          vector < vector <int> > ans(n , vector <int> (m));
          for(int i = 0; i < n; i++){
             for(int j = 0; j < m; j++){
                for(int r = i - k;r <= i + k; r++){
                   for(int c = j - k; c <= j + k; c++){
                      if(r>= 0 && r < n && c >= 0 && c < m){
                         ans[i][j] += mat[r][c];
                      }
                   }
                }
             }
          }
          return ans;
       }
    };
    main(){
       vector<vector<int>> v1 = {{1,2,3},{4,5,6},{7,8,9}};
       Solution ob;
       print_vector(ob.matrixBlockSum(v1, 1));
    }

    输入值

    [[1,2,3],[4,5,6],[7,8,9]]
    1

    输出结果

    [[12, 21, 16, ],[27, 45, 33, ],[24, 39, 28, ],]